結果
問題 | No.922 東北きりきざむたん |
ユーザー | algon_320 |
提出日時 | 2019-11-08 22:14:02 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 183 ms / 2,000 ms |
コード長 | 6,044 bytes |
コンパイル時間 | 2,812 ms |
コンパイル使用メモリ | 186,796 KB |
実行使用メモリ | 43,656 KB |
最終ジャッジ日時 | 2023-10-13 03:56:48 |
合計ジャッジ時間 | 6,360 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,372 KB |
testcase_01 | AC | 2 ms
4,372 KB |
testcase_02 | AC | 1 ms
4,368 KB |
testcase_03 | AC | 1 ms
4,372 KB |
testcase_04 | AC | 2 ms
4,372 KB |
testcase_05 | AC | 2 ms
4,368 KB |
testcase_06 | AC | 2 ms
4,368 KB |
testcase_07 | AC | 2 ms
4,372 KB |
testcase_08 | AC | 2 ms
4,368 KB |
testcase_09 | AC | 37 ms
11,412 KB |
testcase_10 | AC | 26 ms
5,896 KB |
testcase_11 | AC | 32 ms
9,564 KB |
testcase_12 | AC | 16 ms
12,352 KB |
testcase_13 | AC | 9 ms
5,536 KB |
testcase_14 | AC | 58 ms
16,404 KB |
testcase_15 | AC | 12 ms
12,920 KB |
testcase_16 | AC | 138 ms
18,636 KB |
testcase_17 | AC | 140 ms
18,692 KB |
testcase_18 | AC | 146 ms
18,640 KB |
testcase_19 | AC | 139 ms
18,620 KB |
testcase_20 | AC | 144 ms
18,480 KB |
testcase_21 | AC | 141 ms
18,164 KB |
testcase_22 | AC | 146 ms
17,960 KB |
testcase_23 | AC | 180 ms
26,680 KB |
testcase_24 | AC | 183 ms
27,964 KB |
testcase_25 | AC | 143 ms
28,264 KB |
testcase_26 | AC | 136 ms
28,360 KB |
testcase_27 | AC | 140 ms
28,280 KB |
testcase_28 | AC | 33 ms
14,960 KB |
testcase_29 | AC | 130 ms
43,656 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long #define stoi stoll using pii=pair<int,int>; using vi = vector<int>; using vvi = vector<vi>; #define all(c) begin(c),end(c) #define rall(c) rbegin(c),rend(c) #define fore(x,c) for(auto &&x:c) #define rep(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i) #define rrep(i, a, n) for(int i=(int)(n-1);i>=a;--i) #define sz(c) ((int)c.size()) #define contains(c,x) (c.find(x)!=end(c)) #define inseg(l,x,r) ((l)<=(x)&&(x)<(r)) #define dump(...) #define pb push_back #define _ 0 const signed INF_=1001001001; const long long INF=1001001001001001001LL; const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0}; template<class T> ostream& operator<<(ostream &os,const vector<T> &v) { for (auto i = begin(v); i != end(v); i++) os<<*i<<(i==end(v)-1?"":" ");return os;} template<class T> istream& operator>>(istream &is,vector<T> &v) { for (auto i = begin(v); i != end(v); i++) is>>*i;return is;} template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) { is>>p.first>>p.second;return is;} template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;} template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;} template <class T> void psum(T& c) {partial_sum(begin(c), end(c), begin(c));} template<class T> using heap=priority_queue<T,vector<T>,greater<T>>; struct before_main_function { before_main_function() { cin.tie(nullptr); ios::sync_with_stdio(0); cout << setprecision(15) << fixed; // #define endl "\n" } } before_main_function; //------------------8<------------------------------------8<-------------------- struct union_find { vector<int> data; int comp; union_find(int size) : data(size, -1), comp(size) {} void unite(int x, int y) { x = root(x); y = root(y); if(x != y) { if(data[y] < data[x]) swap(x, y); data[x] += data[y]; data[y] = x; comp--; } } bool same(int x, int y) { return root(x) == root(y); } int root(int x) { return data[x] < 0 ? x : (data[x] = root(data[x])); } int size(int x) { return -data[root(x)]; } int components() { return comp; } }; struct LCA { using Query = pii; const vvi &g; vi color; vi ancestor; vector<vector<pair<int, Query>>> query_set; union_find uf; vi res; vi dist; LCA(const vvi &g, vector<Query> &query) : g (g), color (sz(g)), ancestor (sz(g)), query_set (sz(g)), uf (sz(g)), res (sz(query)), dist (sz(g)) { int qs = sz(query); rep(i, 0, qs) { query_set[query[i].first ].emplace_back(i, query[i]); query_set[query[i].second].emplace_back(i, query[i]); } } void visit(int v, int prev, int d) { ancestor[uf.root(v)] = v; for (auto &w : g[v]) { if (w == prev) { continue; } visit(w, v, d + 1); uf.unite(v, w); ancestor[uf.root(v)] = v; } dist[v] = d; color[v] = 1; for (auto &p : query_set[v]) { Query q = p.second; int w = (q.second == v ? q.first : (q.first == v ? q.second : -1)); if (w == -1 || !color[w]) { continue; } res[p.first] = ancestor[uf.root(w)]; } } vi solve(int root) { visit(root, -1, 0); return res; } }; signed main() { int N, M, Q; cin >> N >> M >> Q; vector<vector<int>> G(N); vector<int> num(N); rep(i, 0, M) { int a, b; cin >> a >> b; a--, b--; G[a].push_back(b); G[b].push_back(a); } vector<int> comp(N, -1); vector<int> roots; rep(i, 0, N) { if (comp[i] != -1) continue; static int comp_id = 0; roots.push_back(i); comp_id++; comp[i] = comp_id; auto dfs = [&](auto fun, int v) -> void { comp[v] = comp_id; for (int w : G[v]) { if (comp[w] != -1) continue; fun(fun, w); } }; dfs(dfs, i); } int ans = 0; vector<pii> lca_query; rep(i, 0, Q) { int a, b; cin >> a >> b; a--, b--; if (comp[a] == comp[b]) { lca_query.push_back({a, b}); } else { num[a]++; num[b]++; } } vector<pii> dp(N, pii(0, 0)); for (int root : roots) { auto dfs1 = [&](auto fun, int v, int p) -> void { pii cnt_dist = {num[v], 0}; for (int w : G[v]) { if (w == p) continue; fun(fun, w, v); cnt_dist.first += dp[w].first; cnt_dist.second += dp[w].second + dp[w].first; } dp[v] = cnt_dist; }; dfs1(dfs1, root, -1); auto dfs2 = [&](auto fun, int v, int p, pii upper) -> int { int ret = INF; int tmp = dp[v].second + upper.second; for (int w : G[v]) { if (w == p) continue; int c = dp[v].first - dp[w].first + upper.first; int d = dp[v].second - (dp[w].second + dp[w].first) + c + upper.second; chmin(ret, fun(fun, w, v, {c, d})); } chmin(ret, tmp); return ret; }; int mn = dfs2(dfs2, root, -1, {0, 0}); ans += mn; } { LCA lca(G, lca_query); for (int r : roots) { lca.solve(r); } rep(i, 0, sz(lca_query)) { int a = lca_query[i].first; int b = lca_query[i].second; int l = lca.res[i]; ans += lca.dist[a] + lca.dist[b] - 2 * lca.dist[l]; } } cout << ans << endl; return (0^_^0); }