Submission #1479257
Source Code Expand
#include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <fstream> #include <algorithm> #include <vector> #include <queue> #include <deque> using namespace std; const int MaxN = 2e5 + 5; vector<int> gb[MaxN], gr[MaxN]; int dep[MaxN], fa[MaxN], d[MaxN]; bool safe[MaxN], vis[MaxN]; int main() { ios_base::sync_with_stdio(false); int n, sx, sy; cin >> n >> sx >> sy; for (int i = 1; i < n; ++i) { int x, y; cin >> x >> y; gr[x].emplace_back(y); gr[y].emplace_back(x); } for (int i = 1; i < n; ++i) { int x, y; cin >> x >> y; gb[x].emplace_back(y); gb[y].emplace_back(x); } queue<int> Q; Q.push(sy); fa[sy] = -1; vis[sy] = true; while (!Q.empty()) { int k = Q.front(); for (int x : gb[k]) { if (!vis[x]) { Q.push(x); vis[x] = true; dep[x] = dep[k] + 1; fa[x] = k; } } Q.pop(); } for (int i = 1; i <= n; ++i) { for (int k : gr[i]) { if (![](int x, int y) -> bool { return fa[x] == fa[y] || fa[x] == y || x == fa[y] || fa[fa[x]] == y || x == fa[fa[y]]; } (i, k)) { safe[i] = safe[k] = true; } } } if (safe[sx]) { cout << -1 << endl; return 0; } int ans = 0; memset(d, 0xff, sizeof d); d[sx] = 0; Q.push(sx); while (!Q.empty()) { int k = Q.front(); Q.pop(); if (d[k] >= dep[k]) { continue; } if (safe[k]) { cout << -1 << endl; return 0; } ans = max(ans, dep[k] * 2); for (int x : gr[k]) { if (vis[x] && d[k] + 1 < dep[x] && [](int x, int y) -> bool { return fa[x] == fa[y] || fa[x] == y || x == fa[y] || fa[fa[x]] == y || x == fa[fa[y]]; } (k, x)) { d[x] = d[k] + 1; vis[x] = false; Q.push(x); } } } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Sugigma: The Showdown |
User | Forest_Timber |
Language | C++14 (GCC 5.4.1) |
Score | 1400 |
Code Size | 1952 Byte |
Status | AC |
Exec Time | 159 ms |
Memory | 26996 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 | 125 ms | 24824 KB |
doublestar1 | AC | 120 ms | 24184 KB |
doublestar2 | AC | 125 ms | 24696 KB |
doublestar3 | AC | 116 ms | 24056 KB |
doublestar4 | AC | 126 ms | 25080 KB |
doublestar5 | AC | 131 ms | 25208 KB |
doublestar6 | AC | 119 ms | 24056 KB |
doublestar7 | AC | 118 ms | 24184 KB |
example0 | AC | 5 ms | 11136 KB |
example1 | AC | 4 ms | 11136 KB |
example2 | AC | 4 ms | 11136 KB |
example3 | AC | 4 ms | 10368 KB |
example4 | AC | 4 ms | 11136 KB |
giri0 | AC | 136 ms | 25728 KB |
giri1 | AC | 139 ms | 24704 KB |
giri2 | AC | 136 ms | 24832 KB |
giri3 | AC | 140 ms | 24704 KB |
giri4 | AC | 142 ms | 24576 KB |
giri5 | AC | 147 ms | 25216 KB |
giri6 | AC | 143 ms | 25088 KB |
giri7 | AC | 144 ms | 24960 KB |
giri8 | AC | 146 ms | 24832 KB |
giri9 | AC | 138 ms | 25088 KB |
maxrand0 | AC | 148 ms | 24576 KB |
maxrand1 | AC | 145 ms | 24448 KB |
maxrand2 | AC | 149 ms | 24576 KB |
maxrand3 | AC | 141 ms | 24320 KB |
maxrand4 | AC | 139 ms | 24064 KB |
maxrand5 | AC | 142 ms | 24064 KB |
maxrand6 | AC | 142 ms | 24064 KB |
maxrand7 | AC | 150 ms | 24448 KB |
maxrand8 | AC | 142 ms | 23936 KB |
maxrand9 | AC | 149 ms | 24320 KB |
narashi0 | AC | 138 ms | 24320 KB |
narashi1 | AC | 143 ms | 24448 KB |
narashi2 | AC | 138 ms | 24576 KB |
narashi3 | AC | 139 ms | 24832 KB |
narashi4 | AC | 152 ms | 24832 KB |
narashi5 | AC | 142 ms | 24960 KB |
narashi6 | AC | 145 ms | 24576 KB |
narashi7 | AC | 141 ms | 25216 KB |
narashi8 | AC | 159 ms | 24960 KB |
narashi9 | AC | 147 ms | 24576 KB |
ok0 | AC | 145 ms | 24700 KB |
ok1 | AC | 147 ms | 24828 KB |
ok2 | AC | 144 ms | 24828 KB |
ok3 | AC | 151 ms | 24956 KB |
ok4 | AC | 139 ms | 24576 KB |
ok5 | AC | 148 ms | 24956 KB |
ok6 | AC | 141 ms | 24700 KB |
ok7 | AC | 138 ms | 24448 KB |
ok8 | AC | 145 ms | 25084 KB |
ok9 | AC | 143 ms | 24444 KB |
ouh0 | AC | 120 ms | 25856 KB |
ouh1 | AC | 137 ms | 25728 KB |
ouh2 | AC | 127 ms | 24192 KB |
ouh3 | AC | 142 ms | 25216 KB |
ouh4 | AC | 141 ms | 25472 KB |
ouh5 | AC | 135 ms | 24188 KB |
ouh6 | AC | 139 ms | 24444 KB |
ouh7 | AC | 130 ms | 25088 KB |
ouh8 | AC | 145 ms | 24828 KB |
ouh9 | AC | 139 ms | 24572 KB |
same0 | AC | 149 ms | 24960 KB |
same1 | AC | 148 ms | 24832 KB |
same2 | AC | 142 ms | 25216 KB |
same3 | AC | 142 ms | 25088 KB |
same4 | AC | 138 ms | 24576 KB |
same5 | AC | 146 ms | 24576 KB |
same6 | AC | 144 ms | 24832 KB |
same7 | AC | 146 ms | 24704 KB |
same8 | AC | 136 ms | 24576 KB |
same9 | AC | 152 ms | 25088 KB |
sameline0 | AC | 139 ms | 24192 KB |
sameline1 | AC | 152 ms | 24704 KB |
sameline2 | AC | 139 ms | 24320 KB |
sameline3 | AC | 141 ms | 24320 KB |
sameline4 | AC | 142 ms | 24576 KB |
sameline5 | AC | 143 ms | 24320 KB |
sameline6 | AC | 138 ms | 24192 KB |
sameline7 | AC | 150 ms | 24448 KB |
sameline8 | AC | 144 ms | 24576 KB |
sameline9 | AC | 145 ms | 24704 KB |
star0 | AC | 104 ms | 26484 KB |
star1 | AC | 97 ms | 26484 KB |
star2 | AC | 95 ms | 26484 KB |
star3 | AC | 104 ms | 26484 KB |
star4 | AC | 104 ms | 26612 KB |
star5 | AC | 108 ms | 26740 KB |
star6 | AC | 99 ms | 26740 KB |
star7 | AC | 102 ms | 26484 KB |
star8 | AC | 100 ms | 26484 KB |
star9 | AC | 114 ms | 26996 KB |
supersmall0 | AC | 5 ms | 10368 KB |
supersmall1 | AC | 4 ms | 10368 KB |
supersmall2 | AC | 4 ms | 11136 KB |
supersmall3 | AC | 4 ms | 11136 KB |
supersmall4 | AC | 4 ms | 10368 KB |
supersmall5 | AC | 4 ms | 11136 KB |
supersmall6 | AC | 4 ms | 10368 KB |
supersmall7 | AC | 4 ms | 11136 KB |
supersmall8 | AC | 4 ms | 11136 KB |
supersmall9 | AC | 4 ms | 11136 KB |