結果
問題 | No.529 帰省ラッシュ |
ユーザー |
![]() |
提出日時 | 2017-02-07 23:00:03 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 3,466 ms / 4,500 ms |
コード長 | 10,327 bytes |
コンパイル時間 | 4,501 ms |
コンパイル使用メモリ | 91,272 KB |
実行使用メモリ | 155,092 KB |
最終ジャッジ日時 | 2024-12-25 15:33:55 |
合計ジャッジ時間 | 45,303 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class _484 {public static void main(String[] args) throws IOException {new _484().solve();}void range(int v, int low, int high) {if (v < low || v > high) {throw new RuntimeException();}}void solve() throws IOException {try (final Scanner in = new Scanner(System.in)) {int n = in.nextInt();int m = in.nextInt();int Q = in.nextInt();range(n, 2, 100000);range(m, 1, 200000);range(Q, 2, 200000);SimpleAdjListGraph g = new SimpleAdjListGraph(n, 2*m);for (int i = 0; i < m; i++) {int A = in.nextInt();int B = in.nextInt();range(A, 1, n);range(B, 1, n);g.addEdge(A - 1, B - 1);g.addEdge(B - 1, A - 1);}List<Integer> br = new ArrayList<>();List<List<Integer>> tecomp = new ArrayList<>();g.bridge(br, tecomp);cmp = new int[n];for (int i = 0; i < tecomp.size(); i++) {for (int t : tecomp.get(i)) {cmp[t] = i;}}tree = new HeavyLightDecomposition(tecomp.size());for (int e : br) {tree.addEdge(cmp[g.to[e^0]], cmp[g.to[e^1]]);tree.addEdge(cmp[g.to[e^1]], cmp[g.to[e^0]]);}tree.init();set = new TreeSet[cmp.length];for (int i = 0; i < cmp.length; i++) {set[i] = new TreeSet<>();set[i].add(-1);}seg = new Seg2[tree.getHeavyEdgeCount()];for (int i = 0; i < tree.getHeavyEdgeCount(); i++) {seg[i] = new Seg2(tree.getHeavyEdgeLength(i));for (int j = 0; j < tree.getHeavyEdgeLength(i); j++) {seg[i].update(j, -1);}}while (Q-- > 0) {int t = in.nextInt();range(t, 1, 2);if (t == 1) {int u = in.nextInt();int w = in.nextInt();range(u, 1, n);range(w, 1, 1_000_000_000);int v = cmp[u-1];mp.remove(set[v].last());set[v].add(w);mp.put(set[v].last(), v);seg[tree.getHeavyEdgeId(v)].update(tree.getIndexInHeavyEdge(v), set[v].last());} else if (t == 2) {int S = in.nextInt();int T = in.nextInt();range(S, 1, n);range(T, 1, n);int ans = query(cmp[S-1], cmp[T-1]);remove(ans);System.out.println(ans);}}}}int query(int u, int v) {int ans = -1;while (true) {int hi = tree.getHeavyEdgeId(u);int hj = tree.getHeavyEdgeId(v);if (hi == hj) {int i0 = tree.getIndexInHeavyEdge(u);int i1 = tree.getIndexInHeavyEdge(v);int val = seg[hi].get(Math.min(i0, i1), Math.max(i0, i1) + 1);ans = Math.max(ans, val);break;}int di = tree.getHeavyEdgeDepth(hi);int dj = tree.getHeavyEdgeDepth(hj);if (di >= dj) {int val = seg[hi].get(0, tree.getIndexInHeavyEdge(u) + 1);ans = Math.max(ans, val);u = tree.getParentVertex(hi);} else {int val = seg[hj].get(0, tree.getIndexInHeavyEdge(v) + 1);ans = Math.max(ans, val);v = tree.getParentVertex(hj);}}return ans;}void remove(int ans) {if (ans == -1) return;int v = mp.get(ans);mp.remove(ans);set[v].pollLast();mp.put(set[v].last(), v);seg[tree.getHeavyEdgeId(v)].update(tree.getIndexInHeavyEdge(v), set[v].last());}void put(int v, int w) {mp.remove(set[v].last());set[v].add(w);mp.put(set[v].last(), v);seg[tree.getHeavyEdgeId(v)].update(tree.getIndexInHeavyEdge(v), set[v].last());}int[] cmp;HeavyLightDecomposition tree;TreeMap<Integer, Integer> mp = new TreeMap<>();TreeSet<Integer>[] set;Seg2[] seg;static public class HeavyLightDecomposition {final G g;public HeavyLightDecomposition(final int V) {g = new G(V, 2 * (V - 1));}void addEdge(int s, int t) {g.addEdge(s, t);}int getHeavyEdgeCount() {return g.heavyEdgeCount;}int getHeavyEdgeLength(int heavyEdgeId) {return g.heavyEdge[heavyEdgeId].length;}int getHeavyEdgeDepth(int heavyEdgeId) {return g.heavyEdgeDepth[heavyEdgeId];}int getHeavyEdgeId(int vertexIndex) {return g.belongHeavyEdgeIndex[vertexIndex];}int getIndexInHeavyEdge(int vertexIndex) {return g.heavyEdgeIndex[vertexIndex];}int getParentVertex(int heavyEdgeId) {return g.heavyEdgeParent[g.heavyEdge[heavyEdgeId][0]];}void init() { g.init(); }staticclass G {int m, V, E;int[] head, next, to, childSize, parent;int[] heavyEdgeIndex;int[] belongHeavyEdgeIndex;int[] heavyEdgeParent;int[][] heavyEdge;int[] heavyEdgeVertexCount;int[] heavyEdgeDepth;int heavyEdgeCount;boolean[] vis;int[] st;public G(int V, int E) {head = new int[V];childSize = new int[V];heavyEdgeIndex = new int[V];belongHeavyEdgeIndex = new int[V];heavyEdgeVertexCount = new int[V];heavyEdgeDepth = new int[V];heavyEdgeParent = new int[V];parent = new int[V];next = new int[E];to = new int[E];vis = new boolean[head.length];st = new int[head.length + 1];this.V = V;this.E = E;clear();}public void clear() {m = 0;Arrays.fill(head, -1);}public void addEdge(int s, int t) {next[m] = head[s];head[s] = m;to[m++] = t;}public void init() {calcChildSize(0);initHeavyEdge(0);}public void calcChildSize(final int root) {int sp = 0;parent[root] = -1;st[sp++] = root;while(sp != 0) {final int v = st[--sp];if(!vis[v]) {st[sp++] = v;childSize[v]++;vis[v] = true;for(int e = head[v]; e != -1; e = next[e]) {final int u = to[e];if(!vis[u]) {parent[u] = v;st[sp++] = u;}}}else if(parent[v] != -1) {childSize[parent[v]] += childSize[v];}}}public void initHeavyEdge(final int root) {int sp = 0;st[sp++] = root;Arrays.fill(vis, false);heavyEdgeIndex[root] = 0;belongHeavyEdgeIndex[root] = heavyEdgeCount++;heavyEdgeParent[root] = -1;while(sp != 0) {final int v = st[--sp];if(!vis[v]) {st[sp++] = v;vis[v] = true;heavyEdgeVertexCount[belongHeavyEdgeIndex[v]]++;// System.err.println(belongHeavyEdgeIndex[v] + " " + heavyEdgeVertexCount[belongHeavyEdgeIndex[v]]);int maxChildIndex = -1;int maxChildSize = 0;for(int e = head[v]; e != -1; e = next[e]) {final int u = to[e];if(!vis[u]) {if(maxChildSize < childSize[u]) {maxChildIndex = u;maxChildSize = childSize[u];}// System.err.println(v + " -> " + u + " " + maxChildIndex);st[sp++] = u;}}for(int e = head[v]; e != -1; e = next[e]) {final int u = to[e];if(!vis[u] && maxChildIndex != u) {heavyEdgeIndex[u] = 0;heavyEdgeDepth[heavyEdgeCount] = heavyEdgeDepth[belongHeavyEdgeIndex[v]] + 1;// heavyEdgeVertexCount[heavyEdgeCount] = 1;belongHeavyEdgeIndex[u] = heavyEdgeCount++;heavyEdgeParent[u] = v;}}if(maxChildIndex != -1) {heavyEdgeIndex[maxChildIndex] = heavyEdgeIndex[v] + 1;belongHeavyEdgeIndex[maxChildIndex] = belongHeavyEdgeIndex[v];heavyEdgeParent[maxChildIndex] = heavyEdgeParent[v];}}}heavyEdge = new int[heavyEdgeCount][];for(int i = 0; i < heavyEdgeCount; i++) {heavyEdge[i] = new int[heavyEdgeVertexCount[i]];}for(int i = 0; i < V; i++) {final int j = belongHeavyEdgeIndex[i];// System.err.println(i + " " + j + " " + heavyEdgeIndex[i] + " " + heavyEdge[j].length);heavyEdge[j][heavyEdgeIndex[i]] = i;}}}}static class Seg2 {final int n;final int[] seg;public Seg2(final int n) {this.n = Integer.highestOneBit(n) << 1;seg = new int[this.n << 1];}int get(int l, int r) { return get(l, r, 0, 0, n); }int get(int l, int r, int k, int curL, int curR) {if(curR <= l || curL >= r) return -1;if(l <= curL && curR <= r) { return seg[k]; }final int curM = (curL + curR) / 2;int lv = get(l, r, 2 * k + 1, curL, curM);int rv = get(l, r, 2 * k + 2, curM, curR);return Math.max(lv, rv);}void update(int i, int v) {i += n - 1;seg[i] = v;while(i != 0) {i = (i - 1) / 2;seg[i] = Math.max(seg[2*i+1], seg[2*i+2]);}}}static class SimpleAdjListGraph {int m, V, E;int[] head, next, to;public SimpleAdjListGraph(int V, int E) {head = new int[V];next = new int[E];to = new int[E];this.V = V;this.E = E;clear();}public void clear() {m = 0;Arrays.fill(head, -1);}public void addEdge(int s, int t) {next[m] = head[s];head[s] = m;to[m++] = t;}// 橋,二重辺連結成分分解// http://www.prefield.com/algorithm/graph/bridge.htmlvoid bridge(List<Integer> br, List<List<Integer>> tecomp) {final int n = head.length;int[] num = new int[n];boolean[] inS = new boolean[n];Stack<Integer> roots = new Stack<Integer>(), S = new Stack<Integer>();int time = 0;for(int i = 0; i < n; i++) if(num[i] == 0) {visitBridge(i, n, br, tecomp, roots, S, inS, num, time);br.remove(br.size() - 1);}}private void visitBridge(int v, int u, List<Integer> br,List<List<Integer>> tecomp, Stack<Integer> roots, Stack<Integer> S,boolean[] inS, int[] num, int time) {num[v] = ++time;S.push(v);inS[v] = true;roots.push(v);int eu = -1;for(int e = head[v]; e != -1; e = next[e]) {int w = to[e];if(w == u) { eu = e; }if(num[w] == 0) {visitBridge(w, v, br, tecomp, roots, S, inS, num, time);}else if(u != w && inS[w]) {while(num[roots.peek()] > num[w]) {roots.pop();}}}if(v == roots.peek()) {br.add(eu);List<Integer> xs = new ArrayList<Integer>();while(true) {int w = S.pop();inS[w] = false;xs.add(w);if(v == w) break;}tecomp.add(xs);roots.pop();}}}// for debugstatic void dump(Object... o) {System.err.println(Arrays.deepToString(o));}}