Submission #8801786
Source Code Expand
// #define DEBUGGING
#include <bits/stdc++.h>
#define endl '\n'
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()
template <typename T> using V = std::vector<T>;
template <typename T> using VV = V<V<T>>;
using ll = std::int64_t;
using ull = std::uint64_t;
using PLL = std::pair<ll, ll>;
using TLL = std::tuple<ll, ll, ll>;
template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return std::min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return std::max(t, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return std::max(low, std::min(high, t)); }
template <typename T> void chclamp(T &t, const T &low, const T &high) { return t = clamp(t, low, high); }
namespace init__ { struct InitIO { InitIO() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(30); } } init_io; }
#define mv_rec make_v(init, tail...)
template <typename T> T make_v(T init) { return init; }
template <typename T, typename... Tail> auto make_v(T init, size_t s, Tail... tail) { return V<decltype(mv_rec)>(s, mv_rec); }
#undef mv_rec
using namespace std;
#ifdef DEBUGGING
#include "../../debug/debug.cpp"
#else
#define DEBUG(...) 0
#define DEBUG_SEPARATOR_LINE 0
#endif
void dfs(ll cur, ll pre, const VV<ll> &edges, V<ll> &pars, V<ll> &depth, ll d = 0) {
pars[cur] = pre;
depth[cur] = d;
for(ll nxt : edges[cur]) if(nxt != pre) dfs(nxt, cur, edges, pars, depth, d + 1);
}
bool solve() {
ll N;
cin >> N;
VV<ll> edges(N);
V<ll> digits(N);
for(ll i = 0; i < N - 1; i++) {
ll a, b;
cin >> a >> b;
a--; b--;
edges[a].push_back(b);
edges[b].push_back(a);
digits[a]++;
digits[b]++;
}
V<ll> parents(N);
V<ll> depth(N);
for(ll i = 0; i < N; i++) if(digits[i] != 1) {
dfs(i, -1, edges, parents, depth);
break;
}
set<ll> leaves;
for(ll i = 0; i < N; i++) if(digits[i] == 1) leaves.insert(i);
V<ll> cnts(N);
V<ll> ord(N);
iota(ALL(ord), 0ll);
sort(ALL(ord), [&](ll a, ll b) { return depth[a] > depth[b]; });
for(ll ele : ord) {
if(cnts[ele] == 1) continue;
if(2 <= cnts[ele]) return true;
ll par = parents[ele];
if(par != -1) cnts[par]++;
else return true;
}
return false;
}
int main() {
cout << (solve() ? "First" : "Second") << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Black and White Tree |
User |
kcvlex |
Language |
C++14 (GCC 5.4.1) |
Score |
900 |
Code Size |
2997 Byte |
Status |
AC |
Exec Time |
60 ms |
Memory |
12672 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
900 / 900 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample1.txt, sample2.txt, sample3.txt |
All |
sample1.txt, sample2.txt, sample3.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in3.txt, in30.txt, in31.txt, in32.txt, in33.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt |
Case Name |
Status |
Exec Time |
Memory |
in1.txt |
AC |
56 ms |
12672 KB |
in10.txt |
AC |
52 ms |
12672 KB |
in11.txt |
AC |
51 ms |
11648 KB |
in12.txt |
AC |
5 ms |
1408 KB |
in13.txt |
AC |
55 ms |
11648 KB |
in14.txt |
AC |
54 ms |
11648 KB |
in15.txt |
AC |
53 ms |
11648 KB |
in16.txt |
AC |
52 ms |
11648 KB |
in17.txt |
AC |
54 ms |
11648 KB |
in18.txt |
AC |
54 ms |
11648 KB |
in19.txt |
AC |
55 ms |
11648 KB |
in2.txt |
AC |
58 ms |
12544 KB |
in20.txt |
AC |
55 ms |
11648 KB |
in21.txt |
AC |
60 ms |
12544 KB |
in22.txt |
AC |
58 ms |
12672 KB |
in23.txt |
AC |
51 ms |
11648 KB |
in24.txt |
AC |
50 ms |
11648 KB |
in25.txt |
AC |
54 ms |
11648 KB |
in26.txt |
AC |
49 ms |
11648 KB |
in27.txt |
AC |
50 ms |
11648 KB |
in28.txt |
AC |
1 ms |
256 KB |
in29.txt |
AC |
53 ms |
11648 KB |
in3.txt |
AC |
57 ms |
12544 KB |
in30.txt |
AC |
54 ms |
11648 KB |
in31.txt |
AC |
50 ms |
11648 KB |
in32.txt |
AC |
54 ms |
11648 KB |
in33.txt |
AC |
53 ms |
11648 KB |
in4.txt |
AC |
57 ms |
12544 KB |
in5.txt |
AC |
53 ms |
12672 KB |
in6.txt |
AC |
57 ms |
12544 KB |
in7.txt |
AC |
56 ms |
12672 KB |
in8.txt |
AC |
57 ms |
12544 KB |
in9.txt |
AC |
59 ms |
12544 KB |
sample1.txt |
AC |
1 ms |
256 KB |
sample2.txt |
AC |
1 ms |
256 KB |
sample3.txt |
AC |
1 ms |
256 KB |