Submission #1689665
Source Code Expand
#ifdef DEBUG #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iostream> #include <cassert> #include <sstream> #include <fstream> #include <functional> #include <set> #include <bitset> #include <string> #include <utility> #include <queue> #include <deque> #include <vector> #include <map> #else #include <bits/stdc++.h> #endif #ifdef DEBUG #define debug(...) fprintf(stderr, __VA_ARGS__) #else #define debug(...) #endif #define rep(i, n) for (int i = 0, i##_end_ = (n); i < i##_end_; ++i) #define per(i, n) for (int i = (n) - 1; i >= 0; --i) #define forn(i, l, r) for (int i = (l), i##_end_ = (r); i <= i##_end_; ++i) #define nrof(i, r, l) for (int i = (r), i##_end_ = (l); i >= i##_end_; --i) #define X first #define Y second #define mp make_pair #define pb push_back #define SZ(x) (int)((x).size()) #define ALL(x) (x).begin(), (x).end() using namespace std; typedef vector<int> vi; typedef pair<int, int> pii; typedef long long LL; template<typename T> inline bool chkmax(T &x, const T &y) { return x < y && (~x) ? x = y, 1 : 0; } template<typename T> inline bool chkmin(T &x, const T &y) { return x > y ? x = y, 1 : 0; } #ifdef DEBUG char *input_file, *output_file; #endif struct IO { static const int maxn = (1 << 25) + 10; char a[maxn], *s, b[maxn], *t; void INPUT() { s = a; t = b; #ifdef DEBUG FILE *f = fopen(input_file, "r"); a[fread(a, 1, sizeof a, f)] = 0; #else a[fread(a, 1, sizeof a, stdin)] = 0; #endif } void OUTPUT() { #ifdef DEBUG FILE *f = fopen(output_file, "w"); fwrite(b, 1, t - b, f); #else fwrite(b, 1, t - b, stdout); #endif } operator int() { int x = 0; while(*s != '-' && (*s < '0' || *s > '9')) { ++s; } bool f = 0; if(*s == '-') { f = 1; ++s; } while(*s >= '0' && *s <= '9') { (x *= 10) += *s - '0'; ++s; } if(f) { x = -x; } return x; } operator LL() { LL x = 0; while(*s != '-' && (*s < '0' || *s > '9')) { ++s; } bool f = 0; if(*s == '-') { f = 1; ++s; } while(*s >= '0' && *s <= '9') { (x *= 10) += *s - '0'; ++s; } if(f) { x = -x; } return x; } operator char() { while(*s <= 32) { ++s; } char ret = *s; ++s; return ret; } inline void out(int x) { if(!x) { *t++ = '0'; return; } if(x < 0) { *t++ = '-'; x = -x; } static char c[20], *i; i = c; while(x) { int y = x / 10; *i++ = x - y * 10 + '0'; x = y; } while(i != c) { *t++ = *--i; } return; } inline void out(int x, char C) { if(!x) { *t++ = '0'; *t++ = C; return; } if(x < 0) { *t++ = '-'; x = -x; } static char c[20], *i; i = c; while(x) { int y = x / 10; *i++ = x - y * 10 + '0'; x = y; } while(i != c) { *t++ = *--i; } *t++ = C; return; } inline void out(LL x) { if(!x) { *t++ = '0'; return; } if(x < 0) { *t++ = '-'; x = -x; } static char c[20], *i; i = c; while(x) { LL y = x / 10; *i++ = x - y * 10 + '0'; x = y; } while(i != c) { *t++ = *--i; } return; } inline void out(LL x, char C) { if(!x) { *t++ = '0'; *t++ = C; return; } if(x < 0) { *t++ = '-'; x = -x; } static char c[20], *i; i = c; while(x) { LL y = x / 10; *i++ = x - y * 10 + '0'; x = y; } while(i != c) { *t++ = *--i; } *t++ = C; return; } inline void out(char c) { *t++ = c; return; } inline void out(char *s) { while(*s >= ' ') { *t++ = *s++; } return; } }io; void Main(); int main(int argc, char *argv[]) { #ifdef DEBUG input_file = argv[1]; output_file = argv[2]; #endif io.INPUT(); Main(); io.OUTPUT(); return 0; } //---------------------------------------------------------------------------------------head--------------------------------------------------------------------------------------- const int maxn = 2e5 + 100; const int lgn = 19; int n, r1, r2, ans; vi g1[maxn], g2[maxn]; int par1[maxn][lgn], par2[maxn][lgn]; int dep1[maxn], dep2[maxn]; void dfs1(int u = r1, int p = 0) { par1[u][0] = p; forn(i, 1, lgn - 1) { par1[u][i] = par1[par1[u][i - 1]][i - 1]; } dep1[u] = dep1[p] + 1; for (int v: g1[u]) { if(v != p) { dfs1(v, u); } } return; } void dfs2(int u = r2, int p = 0) { par2[u][0] = p; forn(i, 1, lgn - 1) { par2[u][i] = par2[par2[u][i - 1]][i - 1]; } dep2[u] = dep2[p] + 1; for (int v: g2[u]) { if(v != p) { dfs2(v, u); } } return; } int lca(int u, int v) { if(dep2[u] < dep2[v]) { swap(u, v); } int dlt = dep2[u] - dep2[v]; rep(i, lgn) { if((dlt >> i) & 1) { u = par2[u][i]; } } if(u == v) { return u; } per(i, lgn) { if(par2[u][i] != par2[v][i]) { u = par2[u][i], v = par2[v][i]; } } return par2[u][0]; } void dfs3(int u = r1, int p = 0) { debug("dfs3(%d, %d)\n", u, p); chkmax(ans, max(dep1[u], dep2[u]) - 1 << 1); if(dep1[u] >= dep2[u]) { return; } if(p) { int f = lca(u, p); if(dep2[u] + dep2[p] - dep2[f] * 2 > 2) { ans = -1; return; } } for (int v: g1[u]) { if(v != p) { dfs3(v, u); } } return; } void Main() { n = io; r1 = io; r2 = io; rep(i, n - 1) { int u = io, v = io; g1[u].pb(v); g1[v].pb(u); } rep(i, n - 1) { int u = io, v = io; g2[u].pb(v); g2[v].pb(u); } dfs1(); dfs2(); dfs3(); io.out(ans, '\n'); return; }
Submission Info
Submission Time | |
---|---|
Task | E - Sugigma: The Showdown |
User | OMTWOCZWEIXVI |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 5690 Byte |
Status | WA |
Exec Time | 283 ms |
Memory | 70524 KB |
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 | AC | 178 ms | 62200 KB |
doublestar1 | AC | 162 ms | 61560 KB |
doublestar2 | AC | 194 ms | 62072 KB |
doublestar3 | AC | 174 ms | 61432 KB |
doublestar4 | AC | 175 ms | 62456 KB |
doublestar5 | AC | 200 ms | 62584 KB |
doublestar6 | AC | 174 ms | 61432 KB |
doublestar7 | AC | 164 ms | 61560 KB |
example0 | AC | 6 ms | 14592 KB |
example1 | AC | 7 ms | 14592 KB |
example2 | AC | 6 ms | 14592 KB |
example3 | AC | 6 ms | 14592 KB |
example4 | AC | 6 ms | 14592 KB |
giri0 | WA | 201 ms | 62848 KB |
giri1 | AC | 201 ms | 61824 KB |
giri2 | WA | 221 ms | 61952 KB |
giri3 | AC | 205 ms | 61824 KB |
giri4 | AC | 204 ms | 61696 KB |
giri5 | AC | 211 ms | 62208 KB |
giri6 | AC | 200 ms | 62208 KB |
giri7 | AC | 223 ms | 62080 KB |
giri8 | WA | 200 ms | 61952 KB |
giri9 | WA | 242 ms | 62208 KB |
maxrand0 | AC | 185 ms | 62336 KB |
maxrand1 | AC | 173 ms | 62080 KB |
maxrand2 | AC | 180 ms | 62336 KB |
maxrand3 | AC | 176 ms | 61952 KB |
maxrand4 | AC | 167 ms | 61696 KB |
maxrand5 | AC | 171 ms | 61696 KB |
maxrand6 | AC | 172 ms | 61696 KB |
maxrand7 | AC | 181 ms | 62080 KB |
maxrand8 | AC | 174 ms | 61696 KB |
maxrand9 | AC | 183 ms | 62080 KB |
narashi0 | AC | 199 ms | 61440 KB |
narashi1 | AC | 209 ms | 61568 KB |
narashi2 | AC | 216 ms | 61696 KB |
narashi3 | AC | 195 ms | 61952 KB |
narashi4 | AC | 201 ms | 61952 KB |
narashi5 | AC | 189 ms | 62080 KB |
narashi6 | AC | 200 ms | 61696 KB |
narashi7 | AC | 206 ms | 62336 KB |
narashi8 | AC | 224 ms | 62080 KB |
narashi9 | AC | 192 ms | 61696 KB |
ok0 | WA | 229 ms | 69116 KB |
ok1 | WA | 238 ms | 70140 KB |
ok2 | AC | 222 ms | 67068 KB |
ok3 | WA | 244 ms | 70524 KB |
ok4 | WA | 283 ms | 65152 KB |
ok5 | WA | 241 ms | 67068 KB |
ok6 | WA | 232 ms | 67580 KB |
ok7 | WA | 227 ms | 65024 KB |
ok8 | AC | 228 ms | 68860 KB |
ok9 | WA | 224 ms | 67708 KB |
ouh0 | AC | 170 ms | 63488 KB |
ouh1 | WA | 208 ms | 64256 KB |
ouh2 | AC | 185 ms | 64128 KB |
ouh3 | WA | 220 ms | 65024 KB |
ouh4 | AC | 249 ms | 64640 KB |
ouh5 | WA | 239 ms | 67836 KB |
ouh6 | AC | 263 ms | 68988 KB |
ouh7 | WA | 237 ms | 64128 KB |
ouh8 | AC | 247 ms | 67580 KB |
ouh9 | WA | 238 ms | 68988 KB |
same0 | AC | 217 ms | 62080 KB |
same1 | AC | 215 ms | 61824 KB |
same2 | AC | 177 ms | 62208 KB |
same3 | AC | 179 ms | 62208 KB |
same4 | AC | 184 ms | 61696 KB |
same5 | AC | 248 ms | 61696 KB |
same6 | AC | 183 ms | 61952 KB |
same7 | AC | 208 ms | 61696 KB |
same8 | AC | 169 ms | 61696 KB |
same9 | AC | 217 ms | 62208 KB |
sameline0 | AC | 231 ms | 69376 KB |
sameline1 | AC | 273 ms | 69888 KB |
sameline2 | AC | 233 ms | 67712 KB |
sameline3 | AC | 266 ms | 69504 KB |
sameline4 | AC | 257 ms | 69504 KB |
sameline5 | AC | 237 ms | 69120 KB |
sameline6 | AC | 221 ms | 68992 KB |
sameline7 | AC | 261 ms | 68992 KB |
sameline8 | AC | 233 ms | 68352 KB |
sameline9 | AC | 231 ms | 68224 KB |
star0 | AC | 106 ms | 62964 KB |
star1 | AC | 100 ms | 62836 KB |
star2 | AC | 80 ms | 62964 KB |
star3 | AC | 106 ms | 62836 KB |
star4 | AC | 101 ms | 62964 KB |
star5 | AC | 137 ms | 63092 KB |
star6 | AC | 84 ms | 63092 KB |
star7 | AC | 105 ms | 62836 KB |
star8 | AC | 113 ms | 62836 KB |
star9 | AC | 134 ms | 63348 KB |
supersmall0 | AC | 6 ms | 14592 KB |
supersmall1 | AC | 6 ms | 14592 KB |
supersmall2 | AC | 6 ms | 14592 KB |
supersmall3 | AC | 6 ms | 14592 KB |
supersmall4 | AC | 6 ms | 14592 KB |
supersmall5 | AC | 6 ms | 14592 KB |
supersmall6 | AC | 6 ms | 14592 KB |
supersmall7 | AC | 6 ms | 14592 KB |
supersmall8 | AC | 6 ms | 14592 KB |
supersmall9 | AC | 7 ms | 14592 KB |