Submission #1792035
Source Code Expand
#include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> typedef long long ll ; #define rep(i, a, b) for (int i = a; i <= b; ++ i) const int N = 2e5 + 5, M = N * 2 , inf = 1e9 + 7; using namespace std ; bool vis[N], path[N] ; int n, rt, S, e, ter[M], nxt[M], lnk[N], dep[N], fa[N], ans ; struct edge { int x, y ; } ed[N] ; void add(int x, int y) { ter[++ e] = y, nxt[e] = lnk[x], lnk[x] = e ; } void dfs(int p, int las) { for (int i = lnk[p] ; i; i = nxt[i]) if (ter[i] != las) { dep[ter[i]] = dep[p] + 1 ; fa[ter[i]] = p ; dfs(ter[i], p) ; } } void dfs2(int p, int las, int len) { if (ans == inf) return ; if (dep[p] < len) { ans = max(ans, (len - 1) * 2 + 1) ; return ; } if (dep[p] == len) { ans = max(ans, len * 2) ; return ; } if (vis[p]) { ans = inf ; return ; } bool flg = false ; for (int i = lnk[p] ; i; i = nxt[i]) if (ter[i] != las) flg = true, dfs2(ter[i], p, len + 1) ; if (!flg) { ans = max(ans, dep[p] * 2) ; return ; } } bool chk(int x, int y) { if (dep[x] < dep[y]) swap(x, y) ; if (fa[x] == y) return false ; if (fa[fa[x]] == y) return false ; if (fa[x] == fa[y]) return false ; return true ; } int main() { scanf("%d%d%d", &n, &S, &rt) ; rep(i, 1, n - 1) scanf("%d%d", &ed[i].x, &ed[i].y) ; int x, y ; rep(i, 1, n - 1) { scanf("%d%d", &x, &y) ; add(x, y), add(y, x) ; } dfs(rt, 0) ; rep(i, 1, n - 1) if (chk(ed[i].x, ed[i].y)) vis[ed[i].x] = vis[ed[i].y] = true ; rep(i, 1, n) lnk[i] = 0 ; rep(i, 1, e) nxt[i] = 0 ; e = 0 ; rep(i, 1, n - 1) add(ed[i].x, ed[i].y), add(ed[i].y, ed[i].x) ; dfs2(S, 0, 0) ; if (ans == (int) (1e9 + 7)) { printf("-1\n") ; } else printf("%d\n", ans) ; return 0 ; }
Submission Info
Submission Time | |
---|---|
Task | E - Sugigma: The Showdown |
User | mjy0724 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1797 Byte |
Status | WA |
Exec Time | 95 ms |
Memory | 15872 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:60:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d%d", &n, &S, &rt) ; ^ ./Main.cpp:61:53: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] rep(i, 1, n - 1) scanf("%d%d", &ed[i].x, &ed[i].y) ; ^ ./Main.cpp:64:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &x, &y) ; ^
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 | 77 ms | 7424 KB |
doublestar1 | AC | 73 ms | 7168 KB |
doublestar2 | AC | 74 ms | 7296 KB |
doublestar3 | AC | 70 ms | 7168 KB |
doublestar4 | AC | 77 ms | 7424 KB |
doublestar5 | AC | 77 ms | 7424 KB |
doublestar6 | AC | 71 ms | 7168 KB |
doublestar7 | AC | 72 ms | 7168 KB |
example0 | AC | 2 ms | 4352 KB |
example1 | WA | 2 ms | 4352 KB |
example2 | WA | 2 ms | 4352 KB |
example3 | AC | 2 ms | 4352 KB |
example4 | WA | 2 ms | 4352 KB |
giri0 | AC | 80 ms | 7424 KB |
giri1 | AC | 79 ms | 7296 KB |
giri2 | AC | 80 ms | 7424 KB |
giri3 | AC | 81 ms | 7296 KB |
giri4 | AC | 82 ms | 7296 KB |
giri5 | AC | 83 ms | 7424 KB |
giri6 | AC | 83 ms | 7424 KB |
giri7 | AC | 80 ms | 7296 KB |
giri8 | AC | 81 ms | 7424 KB |
giri9 | AC | 81 ms | 7424 KB |
maxrand0 | AC | 80 ms | 7424 KB |
maxrand1 | AC | 79 ms | 7424 KB |
maxrand2 | AC | 80 ms | 7424 KB |
maxrand3 | AC | 78 ms | 7424 KB |
maxrand4 | AC | 76 ms | 7296 KB |
maxrand5 | AC | 77 ms | 7296 KB |
maxrand6 | AC | 77 ms | 7296 KB |
maxrand7 | AC | 80 ms | 7424 KB |
maxrand8 | AC | 76 ms | 7296 KB |
maxrand9 | AC | 79 ms | 7424 KB |
narashi0 | AC | 81 ms | 7296 KB |
narashi1 | AC | 80 ms | 7296 KB |
narashi2 | AC | 79 ms | 7296 KB |
narashi3 | AC | 82 ms | 7296 KB |
narashi4 | AC | 85 ms | 7424 KB |
narashi5 | AC | 83 ms | 7296 KB |
narashi6 | AC | 87 ms | 7424 KB |
narashi7 | AC | 82 ms | 7424 KB |
narashi8 | AC | 85 ms | 7424 KB |
narashi9 | AC | 81 ms | 7296 KB |
ok0 | AC | 88 ms | 14848 KB |
ok1 | AC | 91 ms | 15744 KB |
ok2 | AC | 88 ms | 12800 KB |
ok3 | AC | 90 ms | 15872 KB |
ok4 | AC | 82 ms | 10880 KB |
ok5 | AC | 90 ms | 12544 KB |
ok6 | AC | 93 ms | 13312 KB |
ok7 | AC | 85 ms | 10880 KB |
ok8 | WA | 92 ms | 14208 KB |
ok9 | AC | 87 ms | 13696 KB |
ouh0 | AC | 77 ms | 7936 KB |
ouh1 | AC | 80 ms | 8832 KB |
ouh2 | AC | 76 ms | 10112 KB |
ouh3 | AC | 80 ms | 10240 KB |
ouh4 | AC | 80 ms | 9600 KB |
ouh5 | AC | 83 ms | 13952 KB |
ouh6 | WA | 85 ms | 14848 KB |
ouh7 | AC | 78 ms | 9216 KB |
ouh8 | WA | 87 ms | 13056 KB |
ouh9 | AC | 86 ms | 14848 KB |
same0 | AC | 82 ms | 7168 KB |
same1 | AC | 84 ms | 7168 KB |
same2 | AC | 81 ms | 7296 KB |
same3 | AC | 81 ms | 7296 KB |
same4 | AC | 79 ms | 7168 KB |
same5 | AC | 82 ms | 7168 KB |
same6 | AC | 79 ms | 7168 KB |
same7 | AC | 83 ms | 7168 KB |
same8 | AC | 76 ms | 7168 KB |
same9 | AC | 85 ms | 7296 KB |
sameline0 | AC | 88 ms | 15232 KB |
sameline1 | AC | 95 ms | 15360 KB |
sameline2 | AC | 87 ms | 13184 KB |
sameline3 | AC | 88 ms | 14208 KB |
sameline4 | AC | 89 ms | 14976 KB |
sameline5 | AC | 90 ms | 14848 KB |
sameline6 | AC | 87 ms | 12160 KB |
sameline7 | AC | 94 ms | 14592 KB |
sameline8 | AC | 92 ms | 13312 KB |
sameline9 | AC | 89 ms | 12160 KB |
star0 | AC | 73 ms | 7168 KB |
star1 | AC | 72 ms | 7168 KB |
star2 | AC | 71 ms | 7168 KB |
star3 | AC | 72 ms | 7168 KB |
star4 | AC | 75 ms | 7168 KB |
star5 | AC | 76 ms | 7168 KB |
star6 | AC | 74 ms | 7168 KB |
star7 | AC | 74 ms | 7168 KB |
star8 | AC | 73 ms | 7168 KB |
star9 | AC | 75 ms | 7296 KB |
supersmall0 | AC | 2 ms | 4352 KB |
supersmall1 | AC | 2 ms | 4352 KB |
supersmall2 | AC | 2 ms | 4352 KB |
supersmall3 | WA | 2 ms | 4352 KB |
supersmall4 | AC | 2 ms | 4352 KB |
supersmall5 | WA | 2 ms | 4352 KB |
supersmall6 | AC | 2 ms | 4352 KB |
supersmall7 | AC | 2 ms | 4352 KB |
supersmall8 | WA | 2 ms | 4352 KB |
supersmall9 | WA | 2 ms | 4352 KB |