提出 #1425431

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
set<int> pathAB;
set<int> hasA;
vector<int> adj[100005];
int cameFrom[100006];
bool visited[100005];
int n;

void gogo(int v){
    visited[v] = true;
    hasA.insert(v);
    for(int i = 0; i < adj[v].size(); i++){
        if(!visited[adj[v][i]] && pathAB.find(adj[v][i]) == pathAB.end()){
            gogo(adj[v][i]);
        }
    }
}
int main(){
    memset(cameFrom, 0, sizeof(cameFrom));
    memset(visited, 0, sizeof(visited));
    ios_base::sync_with_stdio(false);
    cin >> n;
    for(int i = 0; i < n-1; i++){
        int a,b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    queue<int> q;
    cameFrom[1] = -1;
    q.push(1);
    bool brk = false;
    visited[1]= true;
    while(q.size()){
        int curr = q.back();
        cout << curr << endl;
        q.pop();
        for(int i = 0; i < adj[curr].size(); i++){
            if(!visited[adj[curr][i]]){
                visited[adj[curr][i]]= true;
                cameFrom[adj[curr][i]] = curr;
                q.push(adj[curr][i]);
                if(adj[curr][i] == n){
                    brk=true;
                    break;
                }
            }
        }
        if(brk)break;
    }
    int ff = n;
    while(cameFrom[ff] != -1){
        pathAB.insert(ff);
        ff = cameFrom[ff];
    }
    pathAB.insert(1);
    pathAB.insert(n);
    memset(visited,false,sizeof(visited));
    gogo(1);
    int aSize = hasA.size() + (pathAB.size() - 1) /  2,
        bSize = n - aSize;
    if(aSize > bSize){
        cout << "Fennec";
    }else cout << "Snuke";
    return 0;
}

提出情報

ジャッジ結果