• + 1 comment

    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();
      }
    }