Submission #1807199
Source Code Expand
#include <cstdio> #include <algorithm> const int N = 2e5 + 5; inline int Get() { char ch; while ((ch = getchar()) < '0' || ch > '9'); int Num = ch - '0'; while ((ch = getchar()) >= '0' && ch <= '9') Num = (Num << 3) + (Num << 1) + ch - '0'; return Num; } int n, strA, strB, w[N][2], que[N], qn, vis[N], flag[N], ans; struct Graph{ int tot, first[N], next[N << 1], end[N << 1], dist[N], fa[N], sze[N], dfn[N]; inline void AddEdge(int x, int y) { next[++tot] = first[x], first[x] = tot, end[tot] = y; next[++tot] = first[y], first[y] = tot, end[tot] = x; } void Dfs(int x) { que[qn = 1] = x, fa[x] = 0, dist[x] = 0; for (int ql = 1, u; u = que[ql], ql <= qn; sze[u] = 1, ++ql) for (int k = first[u], v; v = end[k], k; k = next[k]) if (v != fa[u]) fa[v] = u, dist[v] = dist[u] + 1, que[++qn] = v; for (int qr = qn, u; u = que[qr], qr > 1; --qr) sze[fa[u]] += sze[u]; dfn[x] = 1; for (int ql = 1, u, cur; u = que[ql], cur = dfn[u], ql <= qn; ++ql) for (int k = first[u], v; v = end[k], k; k = next[k]) if (v != fa[u]) dfn[v] = cur + 1, cur += sze[v]; } inline bool check(int x, int y) { if (dist[x] < dist[y]) std :: swap(x, y); if (dist[x] - dist[y] > 2) return true; if (dfn[y] <= dfn[x] && dfn[x] < dfn[y] + sze[y]) return false; if (fa[x] == fa[y]) return false; return true; } }A, B; int main() { n = Get(), strA = Get(), strB = Get(); for (int i = 1; i < n; ++i) w[i][0] = Get(), w[i][1] = Get(); for (int i = 1; i < n; ++i) B.AddEdge(Get(), Get()); B.Dfs(strB); for (int k = 1; k <= n; ++k) if (B.check(w[k][0], w[k][1])) flag[w[k][0]] = flag[w[k][1]] = true; else A.AddEdge(w[k][0], w[k][1]); que[qn = 1] = strA, vis[strA] = true, A.dist[strA] = 0; for (int ql = 1, u; u = que[ql], ql <= qn; ++ql) for (int k = A.first[u], v; v = A.end[k], k; k = A.next[k]) if ((A.dist[v] = A.dist[u] + 1) < B.dist[v] && !vis[v]) vis[v] = true, que[++qn] = v; for (int i = 1; i <= n; ++i) if (vis[i]) { ans = std :: max(ans, B.dist[i] * 2); if (flag[i]) { puts("-1"); return 0; } } printf("%d\n", ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Sugigma: The Showdown |
User | wy1627 |
Language | C++14 (GCC 5.4.1) |
Score | 1400 |
Code Size | 2186 Byte |
Status | AC |
Exec Time | 73 ms |
Memory | 18176 KB |
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 | 54 ms | 18048 KB |
doublestar1 | AC | 52 ms | 17920 KB |
doublestar2 | AC | 52 ms | 18048 KB |
doublestar3 | AC | 50 ms | 17920 KB |
doublestar4 | AC | 53 ms | 18048 KB |
doublestar5 | AC | 54 ms | 18176 KB |
doublestar6 | AC | 51 ms | 17920 KB |
doublestar7 | AC | 50 ms | 17920 KB |
example0 | AC | 3 ms | 14464 KB |
example1 | AC | 3 ms | 14464 KB |
example2 | AC | 3 ms | 14464 KB |
example3 | AC | 3 ms | 14464 KB |
example4 | AC | 3 ms | 14464 KB |
giri0 | AC | 59 ms | 18176 KB |
giri1 | AC | 59 ms | 18048 KB |
giri2 | AC | 60 ms | 18048 KB |
giri3 | AC | 58 ms | 18048 KB |
giri4 | AC | 59 ms | 18048 KB |
giri5 | AC | 61 ms | 18176 KB |
giri6 | AC | 61 ms | 18176 KB |
giri7 | AC | 60 ms | 18048 KB |
giri8 | AC | 73 ms | 18048 KB |
giri9 | AC | 60 ms | 18048 KB |
maxrand0 | AC | 58 ms | 18176 KB |
maxrand1 | AC | 59 ms | 18048 KB |
maxrand2 | AC | 58 ms | 18176 KB |
maxrand3 | AC | 57 ms | 18048 KB |
maxrand4 | AC | 55 ms | 18048 KB |
maxrand5 | AC | 56 ms | 18048 KB |
maxrand6 | AC | 56 ms | 18048 KB |
maxrand7 | AC | 57 ms | 18048 KB |
maxrand8 | AC | 55 ms | 18048 KB |
maxrand9 | AC | 57 ms | 18048 KB |
narashi0 | AC | 58 ms | 18048 KB |
narashi1 | AC | 58 ms | 18048 KB |
narashi2 | AC | 58 ms | 18048 KB |
narashi3 | AC | 59 ms | 18048 KB |
narashi4 | AC | 60 ms | 18048 KB |
narashi5 | AC | 61 ms | 18048 KB |
narashi6 | AC | 62 ms | 18048 KB |
narashi7 | AC | 61 ms | 18176 KB |
narashi8 | AC | 60 ms | 18176 KB |
narashi9 | AC | 59 ms | 18048 KB |
ok0 | AC | 58 ms | 18048 KB |
ok1 | AC | 58 ms | 18048 KB |
ok2 | AC | 59 ms | 18048 KB |
ok3 | AC | 60 ms | 18176 KB |
ok4 | AC | 61 ms | 18048 KB |
ok5 | AC | 60 ms | 18176 KB |
ok6 | AC | 58 ms | 18048 KB |
ok7 | AC | 60 ms | 18048 KB |
ok8 | AC | 59 ms | 18176 KB |
ok9 | AC | 58 ms | 18048 KB |
ouh0 | AC | 53 ms | 17920 KB |
ouh1 | AC | 55 ms | 18048 KB |
ouh2 | AC | 54 ms | 17920 KB |
ouh3 | AC | 57 ms | 18048 KB |
ouh4 | AC | 56 ms | 18048 KB |
ouh5 | AC | 55 ms | 17920 KB |
ouh6 | AC | 57 ms | 18048 KB |
ouh7 | AC | 54 ms | 17920 KB |
ouh8 | AC | 59 ms | 18048 KB |
ouh9 | AC | 58 ms | 18048 KB |
same0 | AC | 62 ms | 18048 KB |
same1 | AC | 61 ms | 18048 KB |
same2 | AC | 60 ms | 18176 KB |
same3 | AC | 58 ms | 18176 KB |
same4 | AC | 57 ms | 18048 KB |
same5 | AC | 62 ms | 18048 KB |
same6 | AC | 58 ms | 18048 KB |
same7 | AC | 61 ms | 18048 KB |
same8 | AC | 55 ms | 18048 KB |
same9 | AC | 63 ms | 18048 KB |
sameline0 | AC | 58 ms | 18048 KB |
sameline1 | AC | 63 ms | 18176 KB |
sameline2 | AC | 56 ms | 18048 KB |
sameline3 | AC | 58 ms | 18048 KB |
sameline4 | AC | 57 ms | 18048 KB |
sameline5 | AC | 58 ms | 18048 KB |
sameline6 | AC | 55 ms | 18048 KB |
sameline7 | AC | 61 ms | 18048 KB |
sameline8 | AC | 59 ms | 18176 KB |
sameline9 | AC | 58 ms | 18176 KB |
star0 | AC | 50 ms | 18048 KB |
star1 | AC | 50 ms | 18048 KB |
star2 | AC | 47 ms | 18048 KB |
star3 | AC | 49 ms | 18048 KB |
star4 | AC | 51 ms | 18048 KB |
star5 | AC | 53 ms | 18048 KB |
star6 | AC | 50 ms | 18048 KB |
star7 | AC | 49 ms | 18048 KB |
star8 | AC | 49 ms | 18048 KB |
star9 | AC | 55 ms | 18176 KB |
supersmall0 | AC | 3 ms | 14464 KB |
supersmall1 | AC | 3 ms | 14464 KB |
supersmall2 | AC | 3 ms | 14464 KB |
supersmall3 | AC | 3 ms | 14464 KB |
supersmall4 | AC | 3 ms | 14464 KB |
supersmall5 | AC | 3 ms | 14464 KB |
supersmall6 | AC | 3 ms | 14464 KB |
supersmall7 | AC | 3 ms | 14464 KB |
supersmall8 | AC | 3 ms | 14464 KB |
supersmall9 | AC | 3 ms | 14464 KB |