Submission #1517501

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define pb         push_back

typedef long long ll;
const ll INF = 1000000000000000000ll;
const ll MOD = 1000000007ll;
const double EPS = 1e-8;

const int MAX_N = 100005;
struct edge{int to, cost;};
typedef pair<int, int> P;

vector<edge> G[MAX_N];
long long d1[MAX_N];
long long d2[MAX_N];

/*
   ダイクストラ法による単一始点最短経路問題solver
n : ノード数
s : 開始ノード(0-indexed)
*/
void dijkstra(int n, int s, long long* d){
	priority_queue<P, vector<P>, greater<P> > que;
	fill(d, d+n, INF);
	d[s] = 0;
	que.push(P(0, s));

	while(!que.empty()){
		P p = que.top(); que.pop();
		int v = p.second;
		if(d[v] < p.first) continue;
		for(int i=0; i < G[v].size(); i++){
			edge e = G[v][i];
			if(d[e.to] > d[v] + e.cost){
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

int main(void) {
	//ios_base::sync_with_stdio(false);
	//cin.tie(0);
	
	int n;
	cin >> n;

	for(int i=0; i<n-1; i++){
		int a, b;
		cin >> a >> b;
		a--;
		b--;

		G[a].pb(edge{b, 1});
		G[b].pb(edge{a, 1});
	}

	dijkstra(n, 0, d1);
	dijkstra(n, n-1, d2);

	ll fennec = 0;
	ll snuke = 0;
	for(int i=0; i<n; i++){
		if(d1[i] <= d2[i]){
			fennec++;
		}else{
			snuke++;
		}
	}

	if(fennec <= snuke){
		puts("Snuke");
	}else{
		puts("Fennec");
	}
	
	return 0;
}

Submission Info

Judge Result