Submission #1424748
Source Code Expand
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
struct HLDecomposition {
vector<set<int>> g; vector<int> vid, head, heavy, parent, depth, inv;
HLDecomposition() {} HLDecomposition(int n) { init(n); }
void init(int n) { g.resize(n);vid.resize(n, -1);head.resize(n);heavy.resize(n, -1);
parent.resize(n);depth.resize(n);inv.resize(n);}
void add(int u, int v) { g[u].insert(v); g[v].insert(u); } void build() { dfs(0, -1); bfs(); }
int dfs(int curr, int prev) { parent[curr] = prev; int sub = 1, max_sub = 0;
for (int next : g[curr]) if (next != prev) { depth[next] = depth[curr] + 1;
int sub_next = dfs(next, curr); sub += sub_next;
if (max_sub < sub_next) max_sub = sub_next, heavy[curr] = next; }return sub;}
void bfs() { int k = 0; queue<int> q({ 0 }); while (!q.empty()) { int h = q.front(); q.pop();
for (int i = h; i != -1; i = heavy[i]) {vid[i] = k++; inv[vid[i]] = i; head[i] = h;
for (int j : g[i]) if (j != parent[i] && j != heavy[i]) q.push(j);}}}
void foreach(int u, int v, function<void(int, int)> f) {
if (vid[u] > vid[v]) swap(u, v); f(max(vid[head[v]], vid[u]), vid[v]);
if (head[u] != head[v]) foreach(u, parent[head[v]], f);}
int ancestor(int u, int d) { while (true) { if (depth[head[u]] > depth[u] - d) {
d -= depth[u] - depth[head[u]] + 1; if (head[u] == 0) return -1; u = parent[head[u]];}
else return inv[vid[u] - d];} }
int lca(int u, int v) { if (vid[u] > vid[v]) swap(u, v); if (head[u] == head[v]) return u;
return lca(u, parent[head[v]]); }
int distance(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; }
int child(int u, int v, int d) {if (depth[u] >= depth[v]) return -1;int dst = distance(u, v);
if (dst < d - 1) return -1;return ancestor(v, dst - d);}};
/*---------------------------------------------------------------------------------------------------
∧_∧
∧_∧ (´<_` ) Welcome to My Coding Space!
( ´_ゝ`) / ⌒i
/ \ | |
/ / ̄ ̄ ̄ ̄/ |
__(__ニつ/ _/ .| .|____
\/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/
int N;
vector<int> E[101010];
int col[101010];
//---------------------------------------------------------------------------------------------------
void dfs(int cu) {
fore(to, E[cu]) if (!col[to]) {
col[to] = col[cu];
dfs(to);
}
}
//---------------------------------------------------------------------------------------------------
void _main() {
cin >> N;
HLDecomposition hld;
hld.init(N);
rep(i, 0, N - 1) {
int a, b; cin >> a >> b;
a--; b--;
hld.add(a, b);
E[a].push_back(b);
E[b].push_back(a);
}
hld.build();
vector<pair<int, int>> v;
rep(i, 0, N) if(hld.distance(0, N - 1) == hld.distance(0, i) + hld.distance(i, N - 1)){
v.push_back({ hld.distance(0, i), i });
}
sort(v.begin(), v.end());
//fore(p, v) printf("%d %d\n", p.first, p.second);
int i = 0;
int j = v.size() - 1;
while (i < j) {
col[v[i].second] = 1;
col[v[j].second] = 2;
i++; j--;
}
if (i == j) col[v[i].second] = 1;
dfs(0);
dfs(N - 1);
fore(p, v) dfs(p.second);
int a = 0, b = 0;
rep(i, 0, N) {
if (col[i] == 1) a++;
else if (col[i] == 2) b++;
}
//printf("<%d %d>\n", a, b);
if (a <= b) printf("Snuke\n");
else printf("Fennec\n");
}
Submission Info
Submission Time |
|
Task |
D - Fennec VS. Snuke |
User |
hamayanhamayan |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
4095 Byte |
Status |
AC |
Exec Time |
102 ms |
Memory |
27508 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
00_example_01.txt, 00_example_02.txt |
All |
00_example_01.txt, 00_example_02.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt |
Case Name |
Status |
Exec Time |
Memory |
00_example_01.txt |
AC |
2 ms |
2688 KB |
00_example_02.txt |
AC |
2 ms |
2688 KB |
01.txt |
AC |
2 ms |
2688 KB |
02.txt |
AC |
2 ms |
2688 KB |
03.txt |
AC |
2 ms |
2688 KB |
04.txt |
AC |
2 ms |
2688 KB |
05.txt |
AC |
71 ms |
20604 KB |
06.txt |
AC |
78 ms |
21884 KB |
07.txt |
AC |
73 ms |
20604 KB |
08.txt |
AC |
79 ms |
21884 KB |
09.txt |
AC |
2 ms |
2688 KB |
10.txt |
AC |
79 ms |
19456 KB |
11.txt |
AC |
88 ms |
20480 KB |
12.txt |
AC |
85 ms |
20992 KB |
13.txt |
AC |
94 ms |
22016 KB |
14.txt |
AC |
92 ms |
21760 KB |
15.txt |
AC |
90 ms |
21888 KB |
16.txt |
AC |
87 ms |
27508 KB |
17.txt |
AC |
102 ms |
27508 KB |
18.txt |
AC |
88 ms |
27508 KB |
19.txt |
AC |
86 ms |
27508 KB |