Submission #2711311

---

Source Code Expand

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric> // accumulate(v.begin(), v.end(), 0)

using namespace std;
#define ll long long

struct Edge{
  int to, cost;
  Edge(int to, int cost) : to(to), cost(cost) {}
};

typedef vector< vector<Edge> > AdjList;
AdjList graph;

const int INF = 1e+8;

vector<int> dist;

bool bellman_ford(int n, int s){ // n: number of edges, s: source
  dist = vector<int>(n, INF);
  dist[s] = 0;
  for(int i=0; i<n; i++){
    for(int v=0; v<n; v++){
      for(int k=0; k<graph[v].size(); k++){
	Edge e = graph[v][k];
	if(dist[v] != INF && dist[e.to] > dist[v] + e.cost){
	  dist[e.to] = dist[v] + e.cost;
	  if(i == n - 1) return true;
	}
      }
    }
  }
  return false;
}

int main(){
  int N;
  cin >> N;
  graph = AdjList(N);
  for(int i=0; i<N-1; i++){
    int from, to;
    cin >> from >> to;
    graph[from-1].push_back(Edge(to-1, 1));
    graph[to-1].push_back(Edge(from-1, 1));
  }

  vector<int> dist1(N);
  bellman_ford(N, 0);
  for(int i=0; i<N; i++)
    dist1[i] = dist[i];
  vector<int> distN(N);
  bellman_ford(N, N-1);
  for(int i=0; i<N; i++)
    distN[i] = dist[i];

  int countF = 0;
  int countS = 0;
  for(int i=0; i<N; i++)
    if(dist1[i] <= distN[i])
      countF++;
    else
      countS++;

  if(countF >= countS)
    cout << "Fennec" << endl;
  else
    cout << "Sunuke" << endl;

  return 0;
}

Submission Info

Judge Result