結果
問題 | No.922 東北きりきざむたん |
ユーザー | noisy_noimin |
提出日時 | 2019-11-08 22:49:40 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 264 ms / 2,000 ms |
コード長 | 5,530 bytes |
コンパイル時間 | 1,396 ms |
コンパイル使用メモリ | 115,452 KB |
実行使用メモリ | 33,000 KB |
最終ジャッジ日時 | 2023-10-13 04:27:11 |
合計ジャッジ時間 | 6,588 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 40 ms
22,632 KB |
testcase_01 | AC | 40 ms
22,560 KB |
testcase_02 | AC | 40 ms
22,512 KB |
testcase_03 | AC | 40 ms
22,512 KB |
testcase_04 | AC | 41 ms
22,632 KB |
testcase_05 | AC | 41 ms
22,544 KB |
testcase_06 | AC | 40 ms
22,484 KB |
testcase_07 | AC | 41 ms
22,516 KB |
testcase_08 | AC | 42 ms
22,496 KB |
testcase_09 | AC | 78 ms
25,000 KB |
testcase_10 | AC | 76 ms
23,872 KB |
testcase_11 | AC | 79 ms
24,584 KB |
testcase_12 | AC | 53 ms
23,920 KB |
testcase_13 | AC | 50 ms
23,024 KB |
testcase_14 | AC | 107 ms
25,808 KB |
testcase_15 | AC | 45 ms
23,824 KB |
testcase_16 | AC | 187 ms
27,596 KB |
testcase_17 | AC | 192 ms
27,736 KB |
testcase_18 | AC | 188 ms
27,660 KB |
testcase_19 | AC | 189 ms
27,664 KB |
testcase_20 | AC | 185 ms
27,688 KB |
testcase_21 | AC | 255 ms
28,112 KB |
testcase_22 | AC | 264 ms
27,920 KB |
testcase_23 | AC | 196 ms
27,736 KB |
testcase_24 | AC | 197 ms
27,612 KB |
testcase_25 | AC | 172 ms
28,404 KB |
testcase_26 | AC | 164 ms
28,564 KB |
testcase_27 | AC | 165 ms
28,452 KB |
testcase_28 | AC | 73 ms
24,492 KB |
testcase_29 | AC | 166 ms
33,000 KB |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <iomanip> #include <string> #include <stack> #include <queue> #include <map> #include <set> #include <cstdio> #include <cstdlib> #include <cmath> #include <climits> #include <cassert> #include <cstdint> #include <numeric> #include <bitset> #include <functional> using namespace std; using ll = long long; using Pll = pair<ll, ll>; using Pii = pair<int, int>; constexpr ll MOD = 1000000007; constexpr long double EPS = 1e-10; constexpr int dyx[4][2] = { { 0, 1}, {-1, 0}, {0,-1}, {1, 0} }; constexpr int N_MAX = 100000; class UnionFind { public: int n; vector<int> par, rank, size; //親, 深さ, その木の要素数 UnionFind(int n): n(n) { for(int i=0;i<n;++i){ par.push_back(i); rank.push_back(0); size.push_back(1); } } //根を求める int find(int x){ if(par[x] == x){ return x; }else{ int p = find(par[x]); size[x] = size[p]; return par[x] = p; } } //xとyの属する集合の併合 void unite(int x, int y){ x = find(x); y = find(y); if(x == y) return; size[x] += size[y]; size[y] = size[x]; if(rank[x] < rank[y]){ par[x] = y; }else{ par[y] = x; if(rank[x] == rank[y]) rank[x]++; } } //同じ集合に属するか否か bool are_same(int x, int y){ return find(x) == find(y); } }; vector<int> graph[N_MAX]; vector<ll> node_weight(N_MAX, 0), subtree_weight(N_MAX, 0); vector<bool> used(N_MAX, false); vector<int> airport(N_MAX, -1); // uf のあるグループに存在する空港の位置 int n, m, q; ll dfs(int node, int par) { used[node] = true; for(int child: graph[node]) { if(child == par) continue; subtree_weight[node] += dfs(child, node); } subtree_weight[node] += node_weight[node]; return subtree_weight[node]; } int find_centroid(int node, int par, int root) { bool is_centroid = true; ll sum_subtree_weight = node_weight[node], biggest_child_weight = 0; int biggest_child = -1; for(int child: graph[node]) { if(child == par) continue; if(subtree_weight[child] > subtree_weight[root]/2) { is_centroid = false; } sum_subtree_weight += subtree_weight[child]; if(biggest_child_weight < subtree_weight[child]) { biggest_child_weight = subtree_weight[child]; biggest_child = child; } } if(subtree_weight[root] - sum_subtree_weight > subtree_weight[root]/2) is_centroid = false; if(is_centroid) return node; return (biggest_child != -1) ? find_centroid(biggest_child, node, root) : node; } class LowestCommonAncestor { public: int root, n, LOG_V_MAX = 30; vector<int> depth; vector<vector<int>> parent; LowestCommonAncestor(int root=0, int n=N_MAX): root(root), n(n) { depth.assign(n, -1); parent.assign(n, vector<int>(LOG_V_MAX, -1)); for(int i=0;i<n;++i) { if(depth[i] == -1) dfs(i, -1, 0); } for(int j=1;j<LOG_V_MAX;++j) { for(int i=0;i<n;++i) { if(parent[i][j-1] == -1) continue; parent[i][j] = parent[parent[i][j-1]][j-1]; } } } void dfs(int node, int par, int d) { depth[node] = d; parent[node][0] = par; for(int child: graph[node]) { int c = child; if(c == par) continue; dfs(c, node, d+1); } } int get_lca(int u, int v) { if(depth[u] > depth[v]) swap(u, v); int depth_diff = depth[v] - depth[u]; for(int j=0;j<LOG_V_MAX;++j) { if(depth_diff & (1 << j)) { v = parent[v][j]; } } if(u == v) return u; for(int j=LOG_V_MAX-1;j>=0;--j) { if(parent[u][j] != parent[v][j]) { u = parent[u][j]; v = parent[v][j]; } } return parent[u][0]; } int get_dist(int u, int v) { return depth[u] + depth[v] - 2*depth[get_lca(u, v)]; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int u, v; cin >> n >> m >> q; UnionFind uf = UnionFind(n); for(int i=0;i<m;++i) { cin >> u >> v; --u; --v; graph[u].emplace_back(v); graph[v].emplace_back(u); uf.unite(u, v); } vector<Pii> qs(q); for(int i=0;i<q;++i){ cin >> qs[i].first >> qs[i].second; --qs[i].first; --qs[i].second; if(!uf.are_same(qs[i].first, qs[i].second)) { ++node_weight[qs[i].first]; ++node_weight[qs[i].second]; } } for(int i=0;i<n;++i) { if(used[i]) continue; dfs(i, -1); int p = uf.find(i); airport[p] = find_centroid(i, -1, i); } LowestCommonAncestor lca = LowestCommonAncestor(); ll ans = 0; for(int i=0;i<q;++i){ tie(u, v) = qs[i]; if(uf.are_same(u, v)) { ans += lca.get_dist(u, v); } else { // u から u 側の airport まで int airport_u = airport[uf.find(u)]; int airport_v = airport[uf.find(v)]; ans += lca.get_dist(u, airport_u); ans += lca.get_dist(v, airport_v); } } cout << ans << endl; }