結果
問題 | No.922 東北きりきざむたん |
ユーザー |
![]() |
提出日時 | 2023-05-21 15:11:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 183 ms / 2,000 ms |
コード長 | 4,855 bytes |
コンパイル時間 | 4,211 ms |
コンパイル使用メモリ | 265,188 KB |
最終ジャッジ日時 | 2025-02-13 03:57:03 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;//using mint = modint1000000007;//const int mod = 1000000007;//using mint = modint998244353;//const int mod = 998244353;//const int INF = 1e9;const long long LINF = 1e18;#define rep(i, n) for (int i = 0; i < (n); ++i)#define rep2(i,l,r)for(int i=(l);i<(r);++i)#define rrep(i, n) for (int i = (n-1); i >= 0; --i)#define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i)#define all(x) (x).begin(),(x).end()#define allR(x) (x).rbegin(),(x).rend()#define endl "\n"#define P pair<int,int>template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }class Tree {public:Tree(int n, int root) : n(n), root(root) {edge.resize(n);for (int i = 0; i < MAXLOGV; i++) parent[i].resize(n);depth.resize(n, -1);}// uとvをつなぐ// lcaを求めることが主目的なので無向グラフとしているvoid unite(int u, int v) {edge[u].push_back(v);edge[v].push_back(u);}// initする// コンストラクタだけじゃなくてこれも呼ばないとlcaが求められないぞvoid init() {rep(i, n) {if (-1 != depth[i])continue;dfs(i, -1, 0);}for (int k = 0; k + 1 < MAXLOGV; k++) {for (int v = 0; v < n; v++) {if (parent[k][v] < 0) parent[k + 1][v] = -1;else parent[k + 1][v] = parent[k][parent[k][v]];}}}// uとvのlcaを求めるint lca(int u, int v) const {if (depth[u] > depth[v]) swap(u, v);for (int k = 0; k < MAXLOGV; k++) {if ((depth[v] - depth[u]) >> k & 1) {v = parent[k][v];}}if (u == v) return u;for (int k = MAXLOGV - 1; k >= 0; k--) {if (parent[k][u] != parent[k][v]) {u = parent[k][u];v = parent[k][v];}}return parent[0][u];}// uのn個親を求めるint pare(int v, int n) {if (depth[v] < n)return -1;n = min(n, depth[v]);int idx = MAXLOGV;while (n) {for (int i = idx - 1; i >= 0; --i) {if (n < (1 << i))continue;if (-1 == parent[i][v])continue;n -= (1 << i);v = parent[i][v];idx = i;break;}}return v;}// uからvに向かってd進んだ頂点を返すint JumpOnTree(int u, int v, int d) {if (0 == d)return u;int distuv = dist(u, v);if (distuv < d)return -1;int l = lca(u, v);if (l == u)return pare(v, distuv - d);if (l == v)return pare(u, d);int distlu = dist(l, u);if (distlu >= d)return pare(u, d);return pare(v, distuv - d);}// uとvの距離を求める// edgeを定義しないといけない時はこれじゃダメint dist(int u, int v) const {int p = lca(u, v);return (depth[u] - depth[p]) + (depth[v] - depth[p]);}//頂点wが頂点u,vのパス上に存在するかbool on_path(int u, int v, int w) {return (dist(u, w) + dist(v, w) == dist(u, v));}int dfs(int v, int p, int d) {int ret = 1;parent[0][v] = p;depth[v] = d;for (int next : edge[v]) {if (next == p) continue;auto get = dfs(next, v, d + 1);ret += get;}return ret;}static const int MAXLOGV = 25;// グラフの隣接リスト表現vector<vector<int>>edge;// 頂点の数int n;// 根ノードの番号int root;// 親ノードvector<int> parent[MAXLOGV];// 根からの深さvector<int> depth;};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, q; cin >> n >> m >> q;vector<vector<int>>to(n);dsu uf(n);Tree tree(n, 0);rep(i, m) {int a, b; cin >> a >> b; a--, b--;to[a].push_back(b);to[b].push_back(a);uf.merge(a, b);tree.unite(a, b);}tree.init();long long ans = 0;vector<int>cnt(n);rep(i, q) {int a, b; cin >> a >> b, a--, b--;if (uf.same(a, b)) {ans += tree.dist(a, b);}else {cnt[a]++;cnt[b]++;}}vector<pair<long long, int>>memo(n);vector<long long>result(n);auto gs = uf.groups();for (auto g : gs) {int root = g[0];// preauto dfs = [&](auto self, int v, int p = -1)->pair<long long, int> {P ret = { 0,cnt[v] };for (auto nv : to[v]) {if (p == nv)continue;auto get = self(self, nv, v);ret.first += get.first + get.second;ret.second += get.second;}return memo[v] = ret;};dfs(dfs, root);int sz = memo[root].second;result[root] = memo[root].first;// mainauto dfs2 = [&](auto self, int v, int p = -1)->void {if (-1 != p) {result[v] = result[p];result[v] += sz - 2 * memo[v].second;}for (auto nv : to[v]) {if (p == nv)continue;self(self, nv, v);}};dfs2(dfs2, root);long long val = LINF;for (int v : g) {chmin(val, result[v]);}ans += val;}cout << ans << endl;return 0;}