You are viewing a single comment's thread. Return to all comments →
java7
import java.io.*; import java.util.*; public class Solution { static class MyBitSet { private final static int ADDRESS_BITS_PER_WORD = 6; private long[] words; private transient int wordsInUse = 0; private static int wordIndex(int bitIndex) { return bitIndex >> ADDRESS_BITS_PER_WORD; } public MyBitSet(int nbits) { words = new long[wordIndex(nbits - 1) + 1]; } public void clear() { while (wordsInUse > 0) words[--wordsInUse] = 0; } public void set(int bitIndex) { int wordIndex = wordIndex(bitIndex); expandTo(wordIndex); words[wordIndex] |= (1L << bitIndex); } private void expandTo(int wordIndex) { int wordsRequired = wordIndex + 1; if (wordsInUse < wordsRequired) { wordsInUse = wordsRequired; } } public void or(MyBitSet set) { int wordsInCommon = Math.min(wordsInUse, set.wordsInUse); if (wordsInUse < set.wordsInUse) { wordsInUse = set.wordsInUse; } for (int i = 0; i < wordsInCommon; i++) { words[i] |= set.words[i]; } if (wordsInCommon < set.wordsInUse) { System.arraycopy(set.words, wordsInCommon, words, wordsInCommon, wordsInUse - wordsInCommon); } } public boolean get(int bitIndex) { int wordIndex = wordIndex(bitIndex); return (wordIndex < wordsInUse) && ((words[wordIndex] & (1L << bitIndex)) != 0); } } static class PS { int opt; int u; int x; int i; } static class QS { int u; int i; public QS(int u, int i) { this.u = u; this.i = i; } } static Set<Integer>[] graph; static int[] indeg; static int[] topo; static int ttot = 1; static void topo_dfs(int node) { topo[ttot++] = node; for (int i = ptr[node]; i > 0; i = nxt[i]) { if (--indeg[succ[i]] == 0) { topo_dfs(succ[i]); } } } static int[] nxt; static int[] succ; static int[] ptr; static int index = 1; static void addedge(int u, int v) { nxt[index] = ptr[u]; ptr[u] = index; succ[index++] = v; } static final int B = 316; static int[] solve2(int[][] queries, int n, int nQue) { int q = queries[0].length - 1; int[] ans = new int[q + 1]; QS[] que = new QS[nQue + 1]; PS[] perform = new PS[q + 1]; int ptot = 0; int qtot = 0; for (int i = 1; i <= q; i++) { perform[ptot] = new PS(); perform[ptot].opt = queries[0][i]; if (perform[ptot].opt <= 2) { perform[ptot].u = queries[1][i]; perform[ptot].x = queries[2][i]; perform[ptot++].i = i; } else { que[qtot++] = new QS(queries[1][i], i); } ans[i] = Integer.MAX_VALUE; } MyBitSet[] b = new MyBitSet[n + 1]; for (int i = n; i > 0; i--) { b[i] = new MyBitSet(320); } boolean[] cover = new boolean[n + 1]; int[] minVal = new int[n + 1]; for (int l = (ptot - 1) - (ptot - 1) % B, r = ptot - 1; l >= 0; r = l - 1, l -= B) { for (int i = n; i > 0; i--) { b[i].clear(); } for (int i = l; i <= r; ++i) { b[perform[i].u].set(i - l); } for (int i = 1; i <= n; i++) { for (int j = ptr[topo[i]]; j > 0; j = nxt[j]) { b[succ[j]].or(b[topo[i]]); } } Arrays.fill(cover, false); for (int i = l; i <= r; i++) { if (perform[i].opt == 1) { cover[perform[i].u] = true; } } for (int i = 1; i <= n; i++) { if (cover[topo[i]]) { for (int j = ptr[topo[i]]; j > 0; j = nxt[j]) { cover[succ[j]] = true; } } } Arrays.fill(minVal, Integer.MAX_VALUE); for (int i = l; i <= r; i++) { if (perform[i].opt == 2) { minVal[perform[i].u] = Math.min(minVal[perform[i].u], perform[i].x); } } for (int i = 1; i <= n; ++i) { for (int j = ptr[topo[i]]; j > 0; j = nxt[j]) { minVal[succ[j]] = Math.min(minVal[succ[j]], minVal[topo[i]]); } } int i = qtot; while (i > 0 && que[i - 1].i > perform[l].i) { i--; } while (i < qtot) { if (que[i].i < perform[r].i) { int j = r; while (perform[j].i > que[i].i) { --j; } for (; j >= l; j--) if (b[que[i].u].get(j - l)) { ans[que[i].i] = Math.min(ans[que[i].i], perform[j].x); if (perform[j].opt == 1) { --qtot; QS temp = que[i]; que[i] = que[qtot]; que[qtot] = temp; break; } } i += j < l ? 1 : 0; } else if (cover[que[i].u]) { int j = r; for (; perform[j].opt == 2 || !b[que[i].u].get(j - l); j--) { if (perform[j].opt == 2 && b[que[i].u].get(j - l)) { ans[que[i].i] = Math.min(ans[que[i].i], perform[j].x); } } ans[que[i].i] = Math.min(ans[que[i].i], perform[j].x); --qtot; QS temp = que[i]; que[i] = que[qtot]; que[qtot] = temp; } else { ans[que[i].i] = Math.min(ans[que[i].i], minVal[que[i].u]); i++; } } } while (qtot-- > 0) { ans[que[qtot].i] = 0; } return ans; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); graph = new Set[n + 1]; Set<Integer>[] parent = new Set[n + 1]; for (int i = 1; i <= n; i++) { graph[i] = new HashSet<>(); parent[i] = new HashSet<>(); } for (int i = 0; i < m; i++) { st = new StringTokenizer(br.readLine()); int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); graph[u].add(v); parent[v].add(u); } int[][] queries = new int[3][q + 1]; int[] convert = new int[n + 1]; int nodes = 0; int op3 = 0; for (int i = 1; i <= q; i++) { st = new StringTokenizer(br.readLine()); queries[0][i] = Integer.parseInt(st.nextToken()); int u = Integer.parseInt(st.nextToken()); if (convert[u] == 0) { nodes++; convert[u] = nodes; } queries[1][i] = convert[u]; if (queries[0][i] <= 2) { int x = Integer.parseInt(st.nextToken()); queries[2][i] = x; } else { op3++; } } for (int u = 1; u <= n; u++) { if (convert[u] == 0) { for (int v : parent[u]) { graph[v].remove(u); graph[v].addAll(graph[u]); } for (int v : graph[u]) { parent[v].remove(u); parent[v].addAll(parent[u]); } parent[u] = null; graph[u] = null; } } indeg = new int[nodes + 1]; boolean[] existDeg = new boolean[nodes + 1]; nxt = new int[m + 1]; ptr = new int[nodes + 1]; succ = new int[m + 1]; for (int u1 = 1; u1 <= n; u1++) { int u = convert[u1]; if (u > 0) { for (int v1 : graph[u1]) { int v = convert[v1]; indeg[v]++; existDeg[v] = true; addedge(u, v); } } } topo = new int[nodes + 1]; for (int i = nodes; i > 0; i--) { if (!existDeg[i]) { topo_dfs(i); } } int[] ans = solve2(queries, nodes, op3); for (int i = 1; i <= q; i++) { if (ans[i] < Integer.MAX_VALUE) { bw.write(ans[i] + "\n"); } } bw.close(); br.close(); } }
Seems like cookies are disabled on this browser, please enable them to open this website
DAG Queries
You are viewing a single comment's thread. Return to all comments →
java7