C++の練習を兼ねて, AtCoder Beginner Contest 264 の 問題E (Blackout 2) を解いてみた.
■感想.
1. 問題Eは, 方針を絞り込めたので, AC版に到達できたと思う.
2. Union-Find木 の 復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 264 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題E/AC版).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using P = pair<int, int>; using vp = vector<P>; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define pb push_back #define a first #define b second int memo[505050], ans[505050]; // https://github.com/atcoder/live_library/blob/master/uf.cpp // UnionFind // coding: https://youtu.be/TdR816rqc3s?t=726 // comment: https://youtu.be/TdR816rqc3s?t=6822 // -> 一部改変. struct UnionFind{ vi d; UnionFind(int n = 0): d(n, -1) {} int find(int x){ return (d[x] < 0) ? x : (d[x] = find(d[x])); } bool unite(int x, int y){ x = find(x); y = find(y); if(x == y) return false; if(d[x] > d[y]) swap(x, y); d[x] += d[y]; d[y] = x; return true; } bool same(int x, int y){ return find(x) == find(y); } int size(int x){ return -d[find(x)]; } }; int main(){ // 1. 入力情報. int N, M, E; scanf("%d %d %d", &N, &M, &E); vp es; rep(i, E){ int u, v; scanf("%d %d", &u, &v); es.pb({u, v}); } int Q; scanf("%d", &Q); vi xs; rep(i, Q){ int x; scanf("%d", &x); --x; xs.pb(x); ++memo[x]; } // 2. 最終状態. // 都市: 頂点 1 ~ N. // 発電所: 頂点 N + 1 ~ N + M. // -> 頂点 0 に 発電所 を 集約. UnionFind uf(N + 2); rep(i, E){ // 電線番号 i が, 最後まで, 残っているか? if(!memo[i]){ // 都市 or 発電所. int a = es[i].a; int b = es[i].b; // 都市 - 都市. if(a <= N && b <= N) uf.unite(a, b); // 都市 - 発電所. if(a <= N && b > N) uf.unite(a, 0); // 発電所 - 発電所(何もしない). } } // 3. 初期化. // -> 最終状態のみ. ans[Q] = uf.size(0); // 4. 逆算. repr(i, Q - 1, 0){ // 電線番号 j. int j = xs[i]; // 都市 or 発電所. int a = es[j].a; int b = es[j].b; // 都市 - 都市. if(a <= N && b <= N){ uf.unite(a, b); ans[i] = uf.size(0); } // 都市 - 発電所. if(a <= N && b > N){ uf.unite(a, 0); ans[i] = uf.size(0); } // 発電所 - 発電所(変化なし). if(a > N) ans[i] = uf.size(0); } // 5. 出力. repx(i, 1, Q + 1) printf("%d\n", ans[i] - 1); return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
[入力例] 5 5 10 2 3 4 10 5 10 6 9 2 9 4 8 1 7 3 6 8 10 1 8 6 3 5 8 10 2 7 [出力例] 4 4 2 2 2 1 ※AtCoderテストケースより [入力例] 3 2 7 1 2 1 3 2 3 1 4 2 5 3 5 4 5 5 4 5 1 3 6 [出力例] 3 3 3 2 0 [入力例] 5 3 10 1 2 3 4 1 5 1 6 1 7 6 7 5 8 2 3 2 5 3 8 8 4 6 3 1 2 10 9 7 [出力例] 5 5 5 5 4 4 2 1 [入力例] 7 5 13 1 2 3 4 5 6 1 7 3 7 5 7 9 10 11 12 1 8 1 10 4 11 6 11 7 12 10 7 11 9 1 2 6 13 12 3 10 [出力例] 7 7 7 6 5 5 5 3 3 0 |
■参照サイト
freee プログラミングコンテスト2022(AtCoder Beginner Contest 264)
Union-Find木