Submission #2869260
Source Code Expand
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
#include <random>
#include <unordered_map>
#include <unordered_set>
#define LOCAL
using namespace std;
//呪文
#define DUMPOUT cerr
#define dump(...) DUMPOUT<<" ";DUMPOUT<<#__VA_ARGS__<<" :["<<__LINE__<<":"<<__FUNCTION__<<"]"<<endl;DUMPOUT<<" ";dump_func(__VA_ARGS__)
typedef unsigned uint; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; typedef pair<string, string> pss;
template <typename _KTy, typename _Ty> ostream& operator << (ostream& ostr, const pair<_KTy, _Ty>& m) { ostr << "{" << m.first << ", " << m.second << "}"; return ostr; }
template <typename _KTy, typename _Ty> ostream& operator << (ostream& ostr, const map<_KTy, _Ty>& m) { if (m.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { ostr << ", " << *itr; } ostr << "}"; return ostr; }
template <typename _KTy, typename _Ty> ostream& operator << (ostream& ostr, const unordered_map<_KTy, _Ty>& m) { if (m.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { ostr << ", " << *itr; } ostr << "}"; return ostr; }
template <typename _Ty> ostream& operator << (ostream& ostr, const vector<_Ty>& v) { if (v.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) { ostr << ", " << *itr; } ostr << "}"; return ostr; }
template <typename _Ty> ostream& operator << (ostream& ostr, const set<_Ty>& s) { if (s.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { ostr << ", " << *itr; } ostr << "}"; return ostr; }
template <typename _Ty> ostream& operator << (ostream& ostr, const unordered_set<_Ty>& s) { if (s.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { ostr << ", " << *itr; } ostr << "}"; return ostr; }
template <typename _Ty> ostream& operator << (ostream& ostr, const stack<_Ty>& s) { if (s.empty()) { ostr << "{ }"; return ostr; } stack<_Ty> t(s); ostr << "{" << t.top(); t.pop(); while (!t.empty()) { ostr << ", " << t.top(); t.pop(); } ostr << "}"; return ostr; }
template <typename _Ty> ostream& operator << (ostream& ostr, const list<_Ty>& l) { if (l.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << l.front(); for (auto itr = ++l.begin(); itr != l.end(); ++itr) { ostr << ", " << *itr; } ostr << "}"; return ostr; }
template <typename _KTy, typename _Ty> istream& operator >> (istream& istr, pair<_KTy, _Ty>& m) { istr >> m.first >> m.second; return istr; }
template <typename _Ty> istream& operator >> (istream& istr, vector<_Ty>& v) { for (size_t i = 0; i < v.size(); i++) istr >> v[i]; return istr; }
namespace aux { // print tuple
template<typename Ty, unsigned N, unsigned L> struct tp { static void print(ostream& os, const Ty& v) { os << get<N>(v) << ", "; tp<Ty, N + 1, L>::print(os, v); } };
template<typename Ty, unsigned N> struct tp<Ty, N, N> { static void print(ostream& os, const Ty& value) { os << get<N>(value); } };
}
template<typename... Tys> ostream& operator<<(ostream& os, const tuple<Tys...>& t) { os << "{"; aux::tp<tuple<Tys...>, 0, sizeof...(Tys)-1>::print(os, t); os << "}"; return os; }
template<typename A, size_t N, typename T> inline void Fill(A(&array)[N], const T &val) { std::fill((T*)array, (T*)(array + N), val); }
void dump_func() { DUMPOUT << endl; }
template <class Head, class... Tail> void dump_func(Head&& head, Tail&&... tail) { DUMPOUT << head; if (sizeof...(Tail) == 0) { DUMPOUT << " "; } else { DUMPOUT << ", "; } dump_func(std::move(tail)...); }
#define PI 3.14159265358979323846
#define EPS 1e-8
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define fake false
struct SXor128 {
unsigned x, y, z, w;
SXor128() { x = 123456789; y = 362436069; z = 521288629; w = 88675123; }
SXor128(int _w) { x = 123456789; y = 362436069; z = 521288629; w = _w; }
void setSeed() { x = 123456789; y = 362436069; z = 521288629; w = 88675123; }
void setSeed(int _w) { x = 123456789; y = 362436069; z = 521288629; w = _w; }
unsigned nextUInt() {
unsigned t = (x ^ (x << 11));
x = y; y = z; z = w;
return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
unsigned nextUInt(unsigned mod) {
unsigned t = (x ^ (x << 11));
x = y; y = z; z = w;
w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
return w % mod;
}
unsigned nextUInt(unsigned l, unsigned r) {
unsigned t = (x ^ (x << 11));
x = y; y = z; z = w;
w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
return w % (r - l + 1) + l;
}
double nextDouble() {
return double(nextUInt()) / UINT_MAX;
}
};
int N;
vector<vector<int>> G;
vector<int> V;
vector<bool> visited;
bool flag;
deque<int> path;
void dfs(int cur) {
if (cur == N - 1) {
flag = true;
path.push_back(cur);
return;
}
visited[cur] = true;
for (int i = 0; i < G[cur].size(); i++) {
int next = G[cur][i];
if (visited[next])
continue;
dfs(next);
if (flag) {
path.push_back(cur);
return;
}
}
}
// 陣地
void points(int& point, int color, int cur) {
if (V[cur] == -color) {
return;
}
if (V[cur] == 0) {
point++;
V[cur] = color;
}
visited[cur] = true;
for (int i = 0; i < G[cur].size(); i++) {
int next = G[cur][i];
if (visited[next])
continue;
points(point, color, next);
}
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cin >> N;
G.resize(N);
V.resize(N, 0);
visited.resize(N, false);
flag = false;
REP(i, N - 1) {
int v, w;
cin >> v >> w;
v--; w--;
G[v].push_back(w);
G[w].push_back(v);
}
dfs(0);
reverse(all(path));
int turn = 0;
while (!path.empty()) {
if (turn % 2 == 0) {
// fennec
int f = path.front();
path.pop_front();
V[f] = 1;
}
else {
// snuke
int s = path.back();
path.pop_back();
V[s] = -1;
}
turn++;
}
visited = vector<bool>(N, false);
int pFennec = 0;
points(pFennec, 1, 0);
int pSnuke = 0;
points(pSnuke, -1, N - 1);
// どっちが次のターンか
// 奇数なら snuke
if (turn % 2 == 1) {
if (pSnuke <= pFennec)
cout << "Fennec" << endl;
else
cout << "Snuke" << endl;
}
else {
if (pFennec <= pSnuke)
cout << "Snuke" << endl;
else
cout << "Fennec" << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Fennec VS. Snuke |
User |
komori3 |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
6677 Byte |
Status |
AC |
Exec Time |
42 ms |
Memory |
11264 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 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 |
1 ms |
256 KB |
00_example_02.txt |
AC |
1 ms |
256 KB |
01.txt |
AC |
1 ms |
256 KB |
02.txt |
AC |
1 ms |
256 KB |
03.txt |
AC |
1 ms |
256 KB |
04.txt |
AC |
1 ms |
256 KB |
05.txt |
AC |
32 ms |
6528 KB |
06.txt |
AC |
35 ms |
6912 KB |
07.txt |
AC |
32 ms |
6528 KB |
08.txt |
AC |
35 ms |
6912 KB |
09.txt |
AC |
1 ms |
256 KB |
10.txt |
AC |
30 ms |
5376 KB |
11.txt |
AC |
35 ms |
5504 KB |
12.txt |
AC |
33 ms |
5760 KB |
13.txt |
AC |
35 ms |
6144 KB |
14.txt |
AC |
36 ms |
6016 KB |
15.txt |
AC |
35 ms |
6016 KB |
16.txt |
AC |
42 ms |
11264 KB |
17.txt |
AC |
42 ms |
11264 KB |
18.txt |
AC |
41 ms |
11264 KB |
19.txt |
AC |
40 ms |
11264 KB |