Submission #1355530
Source Code Expand
#include<bits/stdc++.h> using namespace std; const int inf = 1e9; typedef pair<int,int> pii; int n, x, y, dep[200005], par[20][200005]; int da[200005], db[200005]; vector<int> ra[200005], rb[200005]; vector<pii> red; queue<int> q; void calc (int cur, int prv) { dep[cur] = dep[prv] + 1; par[0][cur] = prv; for(auto &nxt : rb[cur]) { if(nxt == prv) continue; calc(nxt, cur); } } int getdist (int A, int B) { if(dep[A] < dep[B]) swap(A, B); int ret = 0; for(int i=20;i--;) { if(dep[A] - dep[B] >= (1<<i)) { A = par[i][A]; ret += (1<<i); } } if(A == B) return ret; for(int i=20;i--;) { if(par[i][A] != par[i][B]) { A = par[i][A]; B = par[i][B]; ret += (1<<i) * 2; } } return ret + 2; } int main() { scanf("%d%d%d",&n,&x,&y); for(int i=1;i<n;i++) { int A, B; scanf("%d%d",&A,&B); red.push_back({A, B}); ra[A].push_back(B); ra[B].push_back(A); } for(int i=1;i<n;i++) { int A, B; scanf("%d%d",&A,&B); rb[A].push_back(B); rb[B].push_back(A); } calc(1, 0); for(int k=1;k<20;k++) { for(int i=1;i<=n;i++) { par[k][i] = par[k-1][par[k-1][i]]; } } for(int i=1;i<=n;i++) {da[i] = inf; db[i] = inf;} db[y] = 2; q.push(y); while(!q.empty()) { int cur = q.front(); q.pop(); for(auto &nxt : rb[cur]) { if(db[nxt] == inf) { db[nxt] = db[cur] + 2; q.push(nxt); } } } da[x] = 1; q.push(x); while(!q.empty()) { int cur = q.front(); q.pop(); for(auto &nxt : ra[cur]) { if(da[nxt] == inf && db[nxt] > da[cur] + 3) { da[nxt] = da[cur] + 2; q.push(nxt); } } } for(auto &T : red) { int A = T.first, B = T.second; if(getdist(A, B) >= 3 && (da[A] != inf || da[B] != inf)) { puts("-1"); return 0; } } int ans = 0; for(int i=1;i<=n;i++) { if(da[i] != inf) ans = max(ans, db[i]); } printf("%d\n",ans-2); }
Submission Info
Submission Time | |
---|---|
Task | E - Sugigma: The Showdown |
User | khsoo01 |
Language | C++14 (GCC 5.4.1) |
Score | 1400 |
Code Size | 1910 Byte |
Status | AC |
Exec Time | 236 ms |
Memory | 50672 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:41:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d%d",&n,&x,&y); ^ ./Main.cpp:44:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d",&A,&B); ^ ./Main.cpp:51:22: 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 | 166 ms | 42352 KB |
doublestar1 | AC | 157 ms | 41712 KB |
doublestar2 | AC | 167 ms | 42224 KB |
doublestar3 | AC | 144 ms | 41456 KB |
doublestar4 | AC | 159 ms | 42736 KB |
doublestar5 | AC | 172 ms | 42736 KB |
doublestar6 | AC | 156 ms | 41584 KB |
doublestar7 | AC | 166 ms | 41584 KB |
example0 | AC | 8 ms | 26880 KB |
example1 | AC | 8 ms | 26880 KB |
example2 | AC | 8 ms | 26880 KB |
example3 | AC | 8 ms | 26880 KB |
example4 | AC | 8 ms | 26880 KB |
giri0 | AC | 173 ms | 42608 KB |
giri1 | AC | 183 ms | 41456 KB |
giri2 | AC | 173 ms | 41712 KB |
giri3 | AC | 185 ms | 41584 KB |
giri4 | AC | 191 ms | 41456 KB |
giri5 | AC | 196 ms | 42096 KB |
giri6 | AC | 192 ms | 41968 KB |
giri7 | AC | 180 ms | 41840 KB |
giri8 | AC | 190 ms | 41712 KB |
giri9 | AC | 184 ms | 41968 KB |
maxrand0 | AC | 178 ms | 42096 KB |
maxrand1 | AC | 183 ms | 41968 KB |
maxrand2 | AC | 174 ms | 42096 KB |
maxrand3 | AC | 170 ms | 41840 KB |
maxrand4 | AC | 176 ms | 41584 KB |
maxrand5 | AC | 173 ms | 41584 KB |
maxrand6 | AC | 166 ms | 41584 KB |
maxrand7 | AC | 187 ms | 41968 KB |
maxrand8 | AC | 179 ms | 41456 KB |
maxrand9 | AC | 166 ms | 41840 KB |
narashi0 | AC | 185 ms | 41200 KB |
narashi1 | AC | 187 ms | 41328 KB |
narashi2 | AC | 181 ms | 41456 KB |
narashi3 | AC | 189 ms | 41712 KB |
narashi4 | AC | 196 ms | 41712 KB |
narashi5 | AC | 179 ms | 41840 KB |
narashi6 | AC | 210 ms | 41456 KB |
narashi7 | AC | 188 ms | 42096 KB |
narashi8 | AC | 203 ms | 41840 KB |
narashi9 | AC | 187 ms | 41456 KB |
ok0 | AC | 226 ms | 47472 KB |
ok1 | AC | 212 ms | 49008 KB |
ok2 | AC | 220 ms | 45168 KB |
ok3 | AC | 215 ms | 46320 KB |
ok4 | AC | 187 ms | 44016 KB |
ok5 | AC | 229 ms | 45296 KB |
ok6 | AC | 203 ms | 45808 KB |
ok7 | AC | 190 ms | 44272 KB |
ok8 | AC | 236 ms | 46576 KB |
ok9 | AC | 209 ms | 45680 KB |
ouh0 | AC | 152 ms | 42992 KB |
ouh1 | AC | 179 ms | 43760 KB |
ouh2 | AC | 188 ms | 43120 KB |
ouh3 | AC | 203 ms | 44528 KB |
ouh4 | AC | 201 ms | 43888 KB |
ouh5 | AC | 189 ms | 44784 KB |
ouh6 | AC | 224 ms | 46576 KB |
ouh7 | AC | 183 ms | 42992 KB |
ouh8 | AC | 214 ms | 44528 KB |
ouh9 | AC | 209 ms | 46192 KB |
same0 | AC | 191 ms | 41840 KB |
same1 | AC | 189 ms | 41712 KB |
same2 | AC | 186 ms | 42096 KB |
same3 | AC | 191 ms | 42096 KB |
same4 | AC | 185 ms | 41584 KB |
same5 | AC | 183 ms | 41584 KB |
same6 | AC | 180 ms | 41840 KB |
same7 | AC | 181 ms | 41584 KB |
same8 | AC | 197 ms | 41456 KB |
same9 | AC | 197 ms | 42096 KB |
sameline0 | AC | 201 ms | 48624 KB |
sameline1 | AC | 214 ms | 49520 KB |
sameline2 | AC | 206 ms | 50032 KB |
sameline3 | AC | 196 ms | 47088 KB |
sameline4 | AC | 215 ms | 48112 KB |
sameline5 | AC | 207 ms | 48112 KB |
sameline6 | AC | 189 ms | 46704 KB |
sameline7 | AC | 206 ms | 49136 KB |
sameline8 | AC | 206 ms | 48624 KB |
sameline9 | AC | 208 ms | 50672 KB |
star0 | AC | 150 ms | 43504 KB |
star1 | AC | 132 ms | 43376 KB |
star2 | AC | 130 ms | 43504 KB |
star3 | AC | 146 ms | 43376 KB |
star4 | AC | 147 ms | 43504 KB |
star5 | AC | 153 ms | 43760 KB |
star6 | AC | 134 ms | 43632 KB |
star7 | AC | 146 ms | 43376 KB |
star8 | AC | 148 ms | 43376 KB |
star9 | AC | 153 ms | 43888 KB |
supersmall0 | AC | 8 ms | 26880 KB |
supersmall1 | AC | 8 ms | 26880 KB |
supersmall2 | AC | 8 ms | 26880 KB |
supersmall3 | AC | 8 ms | 26880 KB |
supersmall4 | AC | 8 ms | 26880 KB |
supersmall5 | AC | 8 ms | 26880 KB |
supersmall6 | AC | 8 ms | 26880 KB |
supersmall7 | AC | 8 ms | 26880 KB |
supersmall8 | AC | 8 ms | 26880 KB |
supersmall9 | AC | 8 ms | 26880 KB |