Submission #1697377
Source Code Expand
//2017-10-21 //miaomiao // #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <vector> using namespace std; #define pb push_back #define For(i, a, b) for(int i = (a); i <= (int)(b); ++i) #define Forr(i, a, b) for(int i = (a); i >= (int)(b); --i) #define LOG 20 #define N (200000+5) vector<int> G1[N], G2[N]; int n, ans, dep2[N], u1[N], v1[N], f[N][LOG]; bool reach[N]; void Dfs2(int now, int D, int F){ dep2[now] = D; f[now][0] = F; For(i, 1, 18) f[now][i] = f[f[now][i-1]][i-1]; For(i, 0, G2[now].size()-1) if(G2[now][i] != F) Dfs2(G2[now][i], D+1, now); } void Dfs1(int now, int D, int F){ if(dep2[now] <= D) return; reach[now] = true; ans = max(ans, dep2[now]); For(i, 0, G1[now].size()-1) if(G1[now][i] != F) Dfs1(G1[now][i], D+1, now); } int Dis(int u, int v){ if(dep2[u] < dep2[v]) swap(u, v); int ret = 0; Forr(i, 18, 0) if(dep2[f[u][i]] >= dep2[v]){ ret += 1<<i; u = f[u][i]; } if(u == v) return ret; Forr(i, 18, 0) if(f[u][i] ^ f[v][i]){ ret += (1<<i) << 1; u = f[u][i]; v = f[v][i]; } return ret + 2; } void Check(){ int u, v; For(i, 1, n) ++dep2[i]; For(i, 1, n-1){ u = u1[i], v = v1[i]; if(Dis(u, v) >= 3){puts("-1"); return;} if(!reach[u] || !reach[v]) continue; } printf("%d\n", ans<<1); } int main(){ int st1, st2, u, v; scanf("%d%d%d", &n, &st1, &st2); For(i, 1, n-1){ scanf("%d%d", &u, &v); G1[u].pb(v); G1[v].pb(u); u1[i] = u; v1[i] = v; } For(i, 1, n-1){ scanf("%d%d", &u, &v); G2[u].pb(v); G2[v].pb(u); } Dfs2(st2, 0, 0); Dfs1(st1, 0, 0); Check(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Sugigma: The Showdown |
User | miaomiao |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1722 Byte |
Status | WA |
Exec Time | 251 ms |
Memory | 54524 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:74:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d%d", &n, &st1, &st2); ^ ./Main.cpp:77:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &u, &v); ^ ./Main.cpp:82:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &u, &v); ^
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 | 163 ms | 40696 KB |
doublestar1 | AC | 146 ms | 40056 KB |
doublestar2 | AC | 164 ms | 40440 KB |
doublestar3 | AC | 148 ms | 39928 KB |
doublestar4 | AC | 158 ms | 40952 KB |
doublestar5 | AC | 168 ms | 40952 KB |
doublestar6 | AC | 160 ms | 39928 KB |
doublestar7 | AC | 145 ms | 40056 KB |
example0 | AC | 5 ms | 13440 KB |
example1 | AC | 5 ms | 13440 KB |
example2 | WA | 5 ms | 13440 KB |
example3 | AC | 5 ms | 13440 KB |
example4 | AC | 5 ms | 13440 KB |
giri0 | AC | 176 ms | 41344 KB |
giri1 | WA | 175 ms | 40192 KB |
giri2 | AC | 183 ms | 40320 KB |
giri3 | WA | 178 ms | 40320 KB |
giri4 | WA | 184 ms | 40192 KB |
giri5 | WA | 198 ms | 40704 KB |
giri6 | WA | 185 ms | 40704 KB |
giri7 | WA | 178 ms | 40448 KB |
giri8 | AC | 192 ms | 40448 KB |
giri9 | AC | 183 ms | 40704 KB |
maxrand0 | AC | 174 ms | 40704 KB |
maxrand1 | AC | 190 ms | 40576 KB |
maxrand2 | AC | 180 ms | 40704 KB |
maxrand3 | AC | 172 ms | 40320 KB |
maxrand4 | AC | 173 ms | 40192 KB |
maxrand5 | AC | 175 ms | 40192 KB |
maxrand6 | AC | 166 ms | 40192 KB |
maxrand7 | AC | 172 ms | 40448 KB |
maxrand8 | AC | 169 ms | 40064 KB |
maxrand9 | AC | 174 ms | 40448 KB |
narashi0 | WA | 175 ms | 39936 KB |
narashi1 | WA | 176 ms | 40064 KB |
narashi2 | WA | 171 ms | 40192 KB |
narashi3 | WA | 178 ms | 40448 KB |
narashi4 | WA | 185 ms | 40320 KB |
narashi5 | WA | 176 ms | 40576 KB |
narashi6 | WA | 188 ms | 40192 KB |
narashi7 | WA | 189 ms | 40704 KB |
narashi8 | WA | 182 ms | 40448 KB |
narashi9 | WA | 175 ms | 40192 KB |
ok0 | AC | 224 ms | 52476 KB |
ok1 | AC | 209 ms | 54140 KB |
ok2 | WA | 200 ms | 49148 KB |
ok3 | AC | 207 ms | 54524 KB |
ok4 | AC | 197 ms | 45952 KB |
ok5 | AC | 206 ms | 48764 KB |
ok6 | AC | 203 ms | 49916 KB |
ok7 | AC | 194 ms | 45824 KB |
ok8 | WA | 209 ms | 51708 KB |
ok9 | AC | 202 ms | 50428 KB |
ouh0 | WA | 155 ms | 42368 KB |
ouh1 | AC | 194 ms | 43648 KB |
ouh2 | WA | 169 ms | 44672 KB |
ouh3 | AC | 182 ms | 45440 KB |
ouh4 | WA | 191 ms | 44544 KB |
ouh5 | AC | 190 ms | 50684 KB |
ouh6 | WA | 196 ms | 52476 KB |
ouh7 | AC | 180 ms | 43776 KB |
ouh8 | WA | 199 ms | 49788 KB |
ouh9 | AC | 198 ms | 52476 KB |
same0 | AC | 199 ms | 40448 KB |
same1 | AC | 196 ms | 40320 KB |
same2 | AC | 185 ms | 40704 KB |
same3 | AC | 193 ms | 40576 KB |
same4 | AC | 184 ms | 40192 KB |
same5 | AC | 211 ms | 40192 KB |
same6 | AC | 197 ms | 40448 KB |
same7 | AC | 208 ms | 40192 KB |
same8 | AC | 194 ms | 40064 KB |
same9 | AC | 222 ms | 40576 KB |
sameline0 | AC | 239 ms | 53120 KB |
sameline1 | AC | 251 ms | 53632 KB |
sameline2 | AC | 228 ms | 49920 KB |
sameline3 | AC | 231 ms | 51584 KB |
sameline4 | AC | 235 ms | 52992 KB |
sameline5 | AC | 240 ms | 52736 KB |
sameline6 | AC | 230 ms | 48256 KB |
sameline7 | AC | 246 ms | 52224 KB |
sameline8 | AC | 238 ms | 50432 KB |
sameline9 | AC | 237 ms | 48384 KB |
star0 | AC | 150 ms | 41204 KB |
star1 | AC | 133 ms | 41332 KB |
star2 | AC | 130 ms | 41204 KB |
star3 | AC | 146 ms | 41076 KB |
star4 | AC | 146 ms | 41204 KB |
star5 | AC | 154 ms | 41588 KB |
star6 | AC | 135 ms | 41332 KB |
star7 | AC | 138 ms | 41204 KB |
star8 | AC | 136 ms | 41076 KB |
star9 | AC | 149 ms | 41716 KB |
supersmall0 | AC | 5 ms | 13440 KB |
supersmall1 | AC | 5 ms | 13440 KB |
supersmall2 | AC | 5 ms | 13440 KB |
supersmall3 | WA | 5 ms | 13440 KB |
supersmall4 | AC | 5 ms | 13440 KB |
supersmall5 | AC | 5 ms | 13440 KB |
supersmall6 | AC | 5 ms | 13440 KB |
supersmall7 | WA | 5 ms | 13440 KB |
supersmall8 | AC | 5 ms | 13440 KB |
supersmall9 | AC | 5 ms | 13440 KB |