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
AC × 2
AC × 21
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