結果
| 問題 | No.922 東北きりきざむたん |
| ユーザー |
 Mayimg
|
| 提出日時 | 2019-11-10 19:43:53 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 249 ms / 2,000 ms |
| コード長 | 5,968 bytes |
| コンパイル時間 | 3,228 ms |
| コンパイル使用メモリ | 217,564 KB |
| 最終ジャッジ日時 | 2025-01-08 03:51:08 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 26 |
ソースコード
#define _USE_MATH_DEFINES#include <bits/stdc++.h>using namespace std;class UnionFind {private:int siz;vector<int> a;public:UnionFind(int x) : siz(x), a(x, -1) {}int root(int x) {return a[x] < 0 ? x : a[x] = root(a[x]);}bool unite(int x, int y) {x = root(x);y = root(y);if (x == y) return false;siz--;if (a[x] > a[y]) swap(x, y);a[x] += a[y];a[y] =x;return true;}bool same(int x, int y) {return root(x) == root(y);}int size(int x) {return -a[root(x)];}int connected_component() {return siz;}};class LowestCommonAncestor {private:static const int MAX_SIZE = 30;vector<vector<int>> graph;vector<int> parent[MAX_SIZE];vector<int> depth;int bit_length;void copy(const vector<int> g[], int siz) {graph.resize(siz);for (int i = 0; i < siz; ++i) for (int j : g[i]) graph[i].push_back(j);}void copy(const vector<vector<int>>& g, int siz = -1) {if (siz < 0) siz = (int) g.size();graph.resize(siz);for (int i = 0; i < siz; ++i) for (int j : g[i]) graph[i].push_back(j);}void initialize() {int siz = (int) graph.size();int root = 0;bit_length = 1;while ((1 << bit_length) < siz) ++bit_length;for (int i = 0; i < bit_length; ++i) parent[i].resize(siz);depth.assign(siz, -1);dfs(root, -1, 0);for (int i = 0; i < bit_length- 1; ++i) {for (int v = 0; v < siz; ++v) {if (depth[v] == -1) continue;if (parent[i][v] < 0) parent[i + 1][v] = -1;else parent[i + 1][v] = parent[i][parent[i][v]];}}}void dfs(int cur, int par, int d) {parent[0][cur] = par;depth[cur] = d;for (int child : graph[cur]) if (child != par) dfs(child, cur, d + 1);}public:LowestCommonAncestor() {}LowestCommonAncestor(const vector<vector<int>>& g, int siz = -1) { build(g, siz); }LowestCommonAncestor(const vector<int> g[], int siz) { build(g, siz); }void build(const vector<int> g[], int siz) { copy(g, siz); initialize(); }void build(const vector<vector<int>>& g, int siz = -1) { copy(g, siz); initialize(); }int get(int u, int v) {if (depth[u] > depth[v]) swap(u, v);for (int i = 0; i < bit_length; ++i) if (((depth[v] - depth[u]) >> i) & 1) v = parent[i][v];if (u == v) return u;for (int i = bit_length - 1; i >= 0; --i) if (parent[i][u] != parent[i][v]) u = parent[i][u], v = parent[i][v];return parent[0][u];}};using LCA = LowestCommonAncestor;void dfs_depth (int cur, int par, vector<int>& depth, const vector<vector<int>>& g) {for (int child : g[cur]) if (child != par) {depth[child] = depth[cur] + 1;dfs_depth(child, cur, depth, g);}}void dfs1 (int cur, int par, vector<int>& num, vector<long long>& dp, const vector<int>& counts, const vector<vector<int>>& g) {num[cur] += counts[cur];for (int child : g[cur]) if (child != par) {dfs1(child, cur, num, dp, counts, g);num[cur] += num[child];dp[cur] += dp[child] + num[child];}}void dfs2 (int cur, int par, const vector<int>& num, const vector<long long>& dp, const vector<int>& counts, const vector<vector<int>>& g, long longx, long long y, long long& res) {res = min(res, dp[cur] + y);//cerr << cur << " " << dp[cur] << " " << x << endl;for (int child : g[cur]) if (child != par) {long long xx = num[cur] - num[child] + x;long long yy = dp[cur] - (dp[child] + num[child]) + y + xx;dfs2 (child, cur, num, dp, counts, g, xx, yy, res);}}long long calc (const vector<int>& counts, const vector<vector<int>>& g) {long long res = 1LL << 60;int siz = (int) counts.size();vector<int> num(siz);vector<long long> dp(siz);dfs1(0, -1, num, dp, counts, g);dfs2(0, -1, num, dp, counts, g, 0, 0, res);// cerr << "num = ";// for (int i : num) cerr << i << " ";// cerr << endl;// cerr << "dp = ";// for (long long i : dp) cerr << i << " ";// cerr << endl;return res;}signed main() {ios::sync_with_stdio(false); cin.tie(0);int n, m, q;cin >> n >> m >> q;vector<vector<int>> g(n);UnionFind uf(n);for (int i = 0; i < m; i++) {int u, v;cin >> u >> v;--u;--v;g[u].push_back(v);g[v].push_back(u);uf.unite(u, v);}vector<int> in(n, -1), pos(n);vector<vector<int>> group;for (int i = 0; i < n; i++) {int r = uf.root(i);if (in[r] == -1) {in[r] = (int) group.size();group.push_back({});}in[i] = in[r];pos[i] = group[in[i]].size();group[in[i]].push_back(i);}int comp_siz = (int) group.size();vector<int> sizes(comp_siz);vector<vector<int>> comp_count(comp_siz);vector<vector<vector<int>>> comp_g(comp_siz);for (int i = 0; i < comp_siz; i++) {sizes[i] = (int) group[i].size();comp_count[i].resize(sizes[i]);comp_g[i].resize(sizes[i]);}for (int i = 0; i < n; i++) {for (int nbr : g[i]) {comp_g[in[i]][pos[i]].push_back(pos[nbr]);}}vector<vector<pair<int, int>>> query(comp_siz);for (int i = 0; i < q; i++) {int a, b;cin >> a >> b;--a;--b;if (uf.same(a, b)) {query[in[a]].emplace_back(pos[a], pos[b]);} else {++comp_count[in[a]][pos[a]];++comp_count[in[b]][pos[b]];}}long long ans = 0;//cerr << comp_siz << endl;for (int i = 0; i < comp_siz; i++) {//long long dist_in = 0, dist_out = 0;LCA lca(comp_g[i]);vector<int> depth(sizes[i]);dfs_depth(0, -1, depth, comp_g[i]);ans += calc(comp_count[i], comp_g[i]);//dist_out += calc(comp_count[i], comp_g[i]);for (auto p : query[i]) {ans += depth[p.first] + depth[p.second] - depth[lca.get(p.first, p.second)] * 2;//dist_in += depth[p.first] + depth[p.second] - depth[lca.get(p.first, p.second)] * 2;}//cerr << i << " " << dist_in << " " << dist_out << endl;}cout << ans << '\n';return 0;}