Submission #1482142
Source Code Expand
#include<bits/stdc++.h> using namespace std; struct LCA{ vector<vector<int> > g; const int MAX_LOG = 22; vector<vector<int> > lcc; vector<int> dep; vector<int> myr; private: void init2(){ int n = g.size(); for (int i = 0; i + 1 < MAX_LOG; i++){ for (int j = 0; j < n; j++){ if (lcc[i][j] == -1){ lcc[i + 1][j] = -1; continue; } lcc[i + 1][j] = lcc[i][lcc[i][j]]; } } } public: int lca(int a, int b){ if (dep[a] < dep[b]){ swap(a, b); } for (int i = 0; i < MAX_LOG; i++){ if (((dep[a] - dep[b]) >> i) & 1){ a = lcc[i][a]; } } if (a == b){ return a; } for (int i = MAX_LOG - 1; i >= 0; i--){ if (lcc[i][a] != lcc[i][b]){ a = lcc[i][a]; b = lcc[i][b]; } } return lcc[0][a]; } private: int flag_r; inline void dfs(int b, int pr = -1, int d = 0){ for (auto &i : g[b]){ if (i == pr)continue; dfs(i, b, d + 1); } dep[b] = d; lcc[0][b] = pr; myr[b] = flag_r; } public: void init(vector<vector<int> > &tree, int root = 0){ g = tree; myr.resize(tree.size(), -1); flag_r = root; lcc.resize(MAX_LOG, vector<int>(g.size(), 0)); dep.resize(g.size()); dfs(root); init2(); } void init(vector<vector<int> > &tree, vector<int> &root){ g = tree; myr.resize(tree.size(), -1); lcc.resize(MAX_LOG, vector<int>(g.size(), 0)); dep.resize(g.size()); for (int &i : root){ if (myr[i] == -1){ flag_r = i; dfs(i); } } init2(); } int dist(int a, int b){ if (myr[a] != myr[b]){ return -1; } int lc = lca(a, b); return dep[a] + dep[b] - 2 * dep[lc]; } int go(int a, int b){ for (int i = 0; i < MAX_LOG; i++){ if ((b >> i) & 1){ a = lcc[i][a]; } } return a; } }; #define MAX 200002 int n; int x; int y; vector<vector<int> > sigma; vector<vector<int> > sugim; LCA sigmaL; LCA sugimL; bool win[MAX]; vector<vector<int> > vv; queue<int> q; vector<int> ord; bool vis[MAX]; struct UF{ vector<int> belong; vector<int> size; void resize(int n){ belong.assign(n + 1, -1); size.assign(n + 1, 1); } inline int root(int b){ if (belong[b] == -1){ return b; } belong[b] = root(belong[b]); return belong[b]; } void merge(int a, int b){ a = root(a); b = root(b); if (a == b)return; belong[a] = b; size[b] += size[a]; } }; UF uf; int main(){ cin >> n; uf.resize(n); cin >> x >> y; sigma.resize(n,vector<int>()); sugim = sigma; vv = sigma; for (int i = 1; i < n; i++){ int a, b; scanf("%d%d", &a, &b); a--; b--; sigma[a].push_back(b); sigma[b].push_back(a); } for (int i = 1; i < n; i++){ int a, b; scanf("%d%d", &a, &b); a--; b--; sugim[a].push_back(b); sugim[b].push_back(a); } x--; y--; sugimL.init(sugim,y); for (int i = 0; i < n; i++){ for (int &j : sigma[i]){ if (i > j)continue; int d = sugimL.dist(i, j); if (d > 2){ win[i] = true; win[j] = true; continue; } else{ uf.merge(i, j); } } } sigmaL.init(sigma, y); for (int i = 0; i < n; i++){ if (win[i]){ int a = x; int b = i; if (uf.root(a)!=uf.root(b)){ continue; } int lc = sugimL.lca(a, b); int tim; if (uf.root(lc) == uf.root(a)){ tim = sigmaL.dist(a, lc); } else{ tim = sigmaL.dist(a, sugimL.go(b, sugimL.dist(b, lc) - 1)); } int tim2 = sugimL.dist(lc, y); if (tim < tim2){ puts("-1"); return 0; } } } int ans = 0; for (int i = 0; i < n; i++){ if (win[i] == false){ int a = x; int b = i; if (uf.root(a)!= uf.root(b) ){ continue; } int lc = sugimL.lca(a, b); int tim = sigmaL.dist(a, lc); int tim2 = sugimL.dist(lc, y); int cost = sigmaL.dist(a, b); if (tim > tim2){ continue; } if (tim == tim2){ if (b == lc){ ans = max(ans, cost); } } if (tim < tim2){ ans = max(ans, cost + tim2 - tim); } } } cout << 2*ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Sugigma: The Showdown |
User | Kmcode |
Language | C++14 (GCC 5.4.1) |
Score | 1400 |
Code Size | 4120 Byte |
Status | AC |
Exec Time | 624 ms |
Memory | 94324 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:149:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &a, &b); ^ ./Main.cpp:157:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &a, &b); ^
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1400 / 1400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0, example1, example2, example3, example4 |
All | doublestar0, doublestar1, doublestar2, doublestar3, doublestar4, doublestar5, doublestar6, doublestar7, example0, example1, example2, example3, example4, giri0, giri1, giri2, giri3, giri4, giri5, giri6, giri7, giri8, giri9, maxrand0, maxrand1, maxrand2, maxrand3, maxrand4, maxrand5, maxrand6, maxrand7, maxrand8, maxrand9, narashi0, narashi1, narashi2, narashi3, narashi4, narashi5, narashi6, narashi7, narashi8, narashi9, ok0, ok1, ok2, ok3, ok4, ok5, ok6, ok7, ok8, ok9, ouh0, ouh1, ouh2, ouh3, ouh4, ouh5, ouh6, ouh7, ouh8, ouh9, same0, same1, same2, same3, same4, same5, same6, same7, same8, same9, sameline0, sameline1, sameline2, sameline3, sameline4, sameline5, sameline6, sameline7, sameline8, sameline9, star0, star1, star2, star3, star4, star5, star6, star7, star8, star9, supersmall0, supersmall1, supersmall2, supersmall3, supersmall4, supersmall5, supersmall6, supersmall7, supersmall8, supersmall9 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
doublestar0 | AC | 281 ms | 87040 KB |
doublestar1 | AC | 276 ms | 82852 KB |
doublestar2 | AC | 305 ms | 85644 KB |
doublestar3 | AC | 254 ms | 81964 KB |
doublestar4 | AC | 269 ms | 88436 KB |
doublestar5 | AC | 297 ms | 89072 KB |
doublestar6 | AC | 269 ms | 82092 KB |
doublestar7 | AC | 282 ms | 83108 KB |
example0 | AC | 1 ms | 256 KB |
example1 | AC | 1 ms | 256 KB |
example2 | AC | 1 ms | 256 KB |
example3 | AC | 1 ms | 256 KB |
example4 | AC | 1 ms | 256 KB |
giri0 | AC | 249 ms | 88696 KB |
giri1 | AC | 584 ms | 84880 KB |
giri2 | AC | 252 ms | 86020 KB |
giri3 | AC | 589 ms | 84880 KB |
giri4 | AC | 599 ms | 85640 KB |
giri5 | AC | 624 ms | 88304 KB |
giri6 | AC | 610 ms | 87672 KB |
giri7 | AC | 593 ms | 86024 KB |
giri8 | AC | 258 ms | 86656 KB |
giri9 | AC | 253 ms | 87164 KB |
maxrand0 | AC | 354 ms | 88308 KB |
maxrand1 | AC | 348 ms | 87164 KB |
maxrand2 | AC | 361 ms | 88560 KB |
maxrand3 | AC | 342 ms | 86276 KB |
maxrand4 | AC | 339 ms | 84628 KB |
maxrand5 | AC | 341 ms | 85008 KB |
maxrand6 | AC | 338 ms | 84756 KB |
maxrand7 | AC | 346 ms | 87164 KB |
maxrand8 | AC | 336 ms | 84500 KB |
maxrand9 | AC | 384 ms | 86784 KB |
narashi0 | AC | 516 ms | 83864 KB |
narashi1 | AC | 538 ms | 84624 KB |
narashi2 | AC | 502 ms | 84120 KB |
narashi3 | AC | 523 ms | 85896 KB |
narashi4 | AC | 544 ms | 87288 KB |
narashi5 | AC | 517 ms | 86404 KB |
narashi6 | AC | 570 ms | 86400 KB |
narashi7 | AC | 542 ms | 88052 KB |
narashi8 | AC | 553 ms | 87796 KB |
narashi9 | AC | 538 ms | 84752 KB |
ok0 | AC | 269 ms | 91396 KB |
ok1 | AC | 276 ms | 93180 KB |
ok2 | AC | 536 ms | 90748 KB |
ok3 | AC | 281 ms | 94324 KB |
ok4 | AC | 262 ms | 87948 KB |
ok5 | AC | 283 ms | 91888 KB |
ok6 | AC | 272 ms | 90880 KB |
ok7 | AC | 267 ms | 87568 KB |
ok8 | AC | 529 ms | 93424 KB |
ok9 | AC | 271 ms | 89232 KB |
ouh0 | AC | 340 ms | 85416 KB |
ouh1 | AC | 251 ms | 87948 KB |
ouh2 | AC | 351 ms | 82620 KB |
ouh3 | AC | 254 ms | 88456 KB |
ouh4 | AC | 382 ms | 87948 KB |
ouh5 | AC | 263 ms | 87460 KB |
ouh6 | AC | 353 ms | 89876 KB |
ouh7 | AC | 253 ms | 85792 KB |
ouh8 | AC | 386 ms | 91004 KB |
ouh9 | AC | 267 ms | 90764 KB |
same0 | AC | 476 ms | 86528 KB |
same1 | AC | 434 ms | 85640 KB |
same2 | AC | 398 ms | 87924 KB |
same3 | AC | 408 ms | 87796 KB |
same4 | AC | 379 ms | 84500 KB |
same5 | AC | 414 ms | 84752 KB |
same6 | AC | 432 ms | 86148 KB |
same7 | AC | 428 ms | 84880 KB |
same8 | AC | 367 ms | 84120 KB |
same9 | AC | 441 ms | 87416 KB |
sameline0 | AC | 539 ms | 90512 KB |
sameline1 | AC | 511 ms | 94064 KB |
sameline2 | AC | 454 ms | 89736 KB |
sameline3 | AC | 564 ms | 90760 KB |
sameline4 | AC | 452 ms | 93048 KB |
sameline5 | AC | 507 ms | 91144 KB |
sameline6 | AC | 544 ms | 88844 KB |
sameline7 | AC | 516 ms | 91904 KB |
sameline8 | AC | 469 ms | 92148 KB |
sameline9 | AC | 529 ms | 91380 KB |
star0 | AC | 246 ms | 88064 KB |
star1 | AC | 242 ms | 88708 KB |
star2 | AC | 233 ms | 88576 KB |
star3 | AC | 275 ms | 89220 KB |
star4 | AC | 252 ms | 89212 KB |
star5 | AC | 467 ms | 90612 KB |
star6 | AC | 233 ms | 89080 KB |
star7 | AC | 259 ms | 90112 KB |
star8 | AC | 309 ms | 91268 KB |
star9 | AC | 249 ms | 90860 KB |
supersmall0 | AC | 1 ms | 256 KB |
supersmall1 | AC | 1 ms | 256 KB |
supersmall2 | AC | 1 ms | 256 KB |
supersmall3 | AC | 1 ms | 256 KB |
supersmall4 | AC | 1 ms | 256 KB |
supersmall5 | AC | 1 ms | 256 KB |
supersmall6 | AC | 1 ms | 256 KB |
supersmall7 | AC | 1 ms | 256 KB |
supersmall8 | AC | 1 ms | 256 KB |
supersmall9 | AC | 1 ms | 256 KB |