Submission #1482119
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]; } }; #define MAX 200002 int n; int x; int y; vector<vector<int> > sigma; vector<vector<int> > sugim; LCA sigmaL; LCA sugimL; LCA sigmaLL; bool win[MAX]; vector<vector<int> > vv; queue<int> q; vector<int> ord; bool vis[MAX]; int main(){ cin >> 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{ int ll = sugimL.lca(i, j); if (ll != i&&ll != j){ vv[i].push_back(ll); vv[ll].push_back(i); vv[j].push_back(ll); vv[ll].push_back(j); } else{ vv[i].push_back(j); vv[j].push_back(i); } } } } vis[y] = true; q.push(y); while (!q.empty()){ int b = q.front(); q.pop(); for (int &i : sugim[b]){ if (!vis[i]){ vis[i] = true; q.push(i); } } ord.push_back(b); } sigmaL.init(vv, ord); for (int i = 0; i < n; i++){ if (win[i]){ int a = x; int b = i; if (sigmaL.myr[a] != sigmaL.myr[b]){ continue; } int lc = sugimL.lca(a, b); int tim = sigmaL.dist(a, lc); int tim2 = sugimL.dist(lc, y); if (tim == -1){ continue; } if (tim < tim2){ puts("-1"); return 0; } } } return 0; sigmaLL.init(sigma, y); int ans = 0; for (int i = 0; i < n; i++){ if (win[i] == false){ int a = x; int b = i; if (sigmaL.myr[a] != sigmaL.myr[b]){ continue; } int lc = sugimL.lca(a, b); int tim = sigmaLL.dist(a, lc); int tim2 = sugimL.dist(lc, y); int cost = sigmaLL.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 | 0 |
Code Size | 3971 Byte |
Status | RE |
Exec Time | 2113 ms |
Memory | 262400 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:117: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:125: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 | 0 / 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 | TLE | 2111 ms | 86016 KB |
doublestar1 | TLE | 2111 ms | 80292 KB |
doublestar2 | AC | 287 ms | 82060 KB |
doublestar3 | AC | 258 ms | 78508 KB |
doublestar4 | AC | 280 ms | 84852 KB |
doublestar5 | TLE | 2111 ms | 87920 KB |
doublestar6 | TLE | 2111 ms | 79276 KB |
doublestar7 | TLE | 2111 ms | 81828 KB |
example0 | WA | 1 ms | 256 KB |
example1 | WA | 1 ms | 256 KB |
example2 | WA | 1 ms | 256 KB |
example3 | AC | 1 ms | 256 KB |
example4 | WA | 1 ms | 256 KB |
giri0 | AC | 298 ms | 94840 KB |
giri1 | WA | 298 ms | 90512 KB |
giri2 | AC | 305 ms | 91780 KB |
giri3 | WA | 299 ms | 90640 KB |
giri4 | WA | 303 ms | 91144 KB |
giri5 | WA | 313 ms | 94064 KB |
giri6 | WA | 313 ms | 93560 KB |
giri7 | WA | 303 ms | 91784 KB |
giri8 | AC | 315 ms | 92288 KB |
giri9 | AC | 307 ms | 92924 KB |
maxrand0 | AC | 343 ms | 81524 KB |
maxrand1 | AC | 335 ms | 80508 KB |
maxrand2 | AC | 343 ms | 81648 KB |
maxrand3 | AC | 329 ms | 79620 KB |
maxrand4 | AC | 323 ms | 78100 KB |
maxrand5 | AC | 331 ms | 78480 KB |
maxrand6 | AC | 328 ms | 78228 KB |
maxrand7 | AC | 335 ms | 80380 KB |
maxrand8 | AC | 331 ms | 77972 KB |
maxrand9 | AC | 371 ms | 80128 KB |
narashi0 | WA | 299 ms | 89368 KB |
narashi1 | WA | 305 ms | 90128 KB |
narashi2 | WA | 298 ms | 89752 KB |
narashi3 | WA | 302 ms | 91656 KB |
narashi4 | WA | 316 ms | 92920 KB |
narashi5 | WA | 313 ms | 92164 KB |
narashi6 | WA | 314 ms | 91904 KB |
narashi7 | WA | 313 ms | 93812 KB |
narashi8 | WA | 318 ms | 93556 KB |
narashi9 | WA | 301 ms | 90384 KB |
ok0 | AC | 325 ms | 93444 KB |
ok1 | AC | 332 ms | 94972 KB |
ok2 | WA | 327 ms | 94588 KB |
ok3 | AC | 336 ms | 96116 KB |
ok4 | AC | 315 ms | 93196 KB |
ok5 | AC | 335 ms | 95856 KB |
ok6 | AC | 322 ms | 93696 KB |
ok7 | AC | 319 ms | 92176 KB |
ok8 | WA | 339 ms | 96240 KB |
ok9 | AC | 320 ms | 92048 KB |
ouh0 | WA | 271 ms | 91560 KB |
ouh1 | AC | 300 ms | 93964 KB |
ouh2 | WA | 285 ms | 87740 KB |
ouh3 | AC | 307 ms | 93960 KB |
ouh4 | WA | 313 ms | 93708 KB |
ouh5 | AC | 308 ms | 90404 KB |
ouh6 | WA | 305 ms | 92308 KB |
ouh7 | AC | 306 ms | 91424 KB |
ouh8 | WA | 316 ms | 95100 KB |
ouh9 | AC | 314 ms | 93196 KB |
same0 | WA | 300 ms | 92288 KB |
same1 | WA | 294 ms | 91400 KB |
same2 | WA | 303 ms | 93812 KB |
same3 | WA | 309 ms | 93684 KB |
same4 | WA | 294 ms | 90132 KB |
same5 | WA | 296 ms | 90384 KB |
same6 | WA | 300 ms | 91908 KB |
same7 | WA | 296 ms | 90512 KB |
same8 | WA | 293 ms | 89624 KB |
same9 | WA | 306 ms | 93304 KB |
sameline0 | WA | 321 ms | 95888 KB |
sameline1 | WA | 333 ms | 99696 KB |
sameline2 | WA | 321 ms | 95240 KB |
sameline3 | WA | 324 ms | 96264 KB |
sameline4 | WA | 339 ms | 98552 KB |
sameline5 | WA | 324 ms | 96648 KB |
sameline6 | WA | 321 ms | 94348 KB |
sameline7 | WA | 330 ms | 97408 KB |
sameline8 | WA | 335 ms | 97780 KB |
sameline9 | WA | 331 ms | 97012 KB |
star0 | TLE | 2112 ms | 97020 KB |
star1 | TLE | 2110 ms | 96640 KB |
star2 | TLE | 2112 ms | 97020 KB |
star3 | TLE | 2112 ms | 96512 KB |
star4 | TLE | 2112 ms | 97400 KB |
star5 | TLE | 2112 ms | 98416 KB |
star6 | TLE | 2111 ms | 100212 KB |
star7 | TLE | 2112 ms | 96892 KB |
star8 | TLE | 2112 ms | 96640 KB |
star9 | TLE | 2113 ms | 99816 KB |
supersmall0 | AC | 1 ms | 256 KB |
supersmall1 | AC | 1 ms | 256 KB |
supersmall2 | AC | 1 ms | 256 KB |
supersmall3 | WA | 1 ms | 256 KB |
supersmall4 | AC | 1 ms | 256 KB |
supersmall5 | WA | 1 ms | 256 KB |
supersmall6 | RE | 270 ms | 262400 KB |
supersmall7 | RE | 388 ms | 262400 KB |
supersmall8 | WA | 1 ms | 256 KB |
supersmall9 | WA | 1 ms | 256 KB |