Submission #1517498
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, 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
Submission Time | |
---|---|
Task | D - Fennec VS. Snuke |
User | tanutarou |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1415 Byte |
Status | WA |
Exec Time | 97 ms |
Memory | 8260 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | 2560 KB |
00_example_02.txt | AC | 2 ms | 2560 KB |
01.txt | WA | 2 ms | 2560 KB |
02.txt | AC | 2 ms | 2560 KB |
03.txt | AC | 2 ms | 2560 KB |
04.txt | AC | 2 ms | 2560 KB |
05.txt | AC | 74 ms | 6912 KB |
06.txt | AC | 80 ms | 7168 KB |
07.txt | WA | 74 ms | 6784 KB |
08.txt | WA | 80 ms | 7168 KB |
09.txt | AC | 2 ms | 2560 KB |
10.txt | WA | 89 ms | 7528 KB |
11.txt | WA | 90 ms | 7296 KB |
12.txt | WA | 92 ms | 7888 KB |
13.txt | AC | 97 ms | 8176 KB |
14.txt | AC | 97 ms | 8260 KB |
15.txt | WA | 97 ms | 8168 KB |
16.txt | AC | 81 ms | 7296 KB |
17.txt | AC | 81 ms | 7296 KB |
18.txt | AC | 81 ms | 7296 KB |
19.txt | AC | 82 ms | 7296 KB |