結果
問題 | No.529 帰省ラッシュ |
ユーザー |
![]() |
提出日時 | 2017-02-07 23:00:03 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 3,516 ms / 4,500 ms |
コード長 | 10,327 bytes |
コンパイル時間 | 5,206 ms |
コンパイル使用メモリ | 90,332 KB |
実行使用メモリ | 153,820 KB |
最終ジャッジ日時 | 2024-06-07 12:14:34 |
合計ジャッジ時間 | 43,950 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 135 ms
41,268 KB |
testcase_01 | AC | 129 ms
41,516 KB |
testcase_02 | AC | 132 ms
41,260 KB |
testcase_03 | AC | 132 ms
41,472 KB |
testcase_04 | AC | 372 ms
48,644 KB |
testcase_05 | AC | 374 ms
48,364 KB |
testcase_06 | AC | 372 ms
48,536 KB |
testcase_07 | AC | 378 ms
48,280 KB |
testcase_08 | AC | 2,749 ms
98,720 KB |
testcase_09 | AC | 2,743 ms
98,176 KB |
testcase_10 | AC | 3,347 ms
105,016 KB |
testcase_11 | AC | 3,251 ms
104,188 KB |
testcase_12 | AC | 2,639 ms
93,748 KB |
testcase_13 | AC | 2,943 ms
153,820 KB |
testcase_14 | AC | 2,285 ms
85,360 KB |
testcase_15 | AC | 3,516 ms
104,064 KB |
testcase_16 | AC | 3,452 ms
103,152 KB |
testcase_17 | AC | 3,098 ms
128,372 KB |
testcase_18 | AC | 2,946 ms
124,128 KB |
testcase_19 | AC | 3,041 ms
119,700 KB |
ソースコード
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(); } static class 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.html void 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 debug static void dump(Object... o) { System.err.println(Arrays.deepToString(o)); } }