TIMUS submission
unknown
c_cpp
a year ago
1.3 kB
7
Indexable
#include<bits/stdc++.h> using namespace std; using ll=long long; #define pb push_back template <typename T> using Vec = vector<T>; void solve(); int main() { cin.tie(nullptr)->sync_with_stdio(false); ll t; t = 1; while (t--) solve(); } const ll N = 1e3 + 20; Vec<ll> adj[N]; ll allChEven[N]; ll sz[N]; ll n, l; void give(ll res) { if (res == -1) { cout << "First player loses\n"; } else { cout << "First player wins flying to airport " << res << "\n"; } } void dfs (ll i, ll p) { bool all_child_even=true; for (auto& ch : adj[i]) { if (ch != p) { dfs (ch, i); sz[i] += sz[ch]; if (sz[ch]&1) { all_child_even=false; } } } allChEven[i] = all_child_even; sz[i]++; } Vec<ll> possible; ll subsz=0; void dfs2(ll i, ll p) { if (allChEven[i] == true && (subsz-sz[i])%2==0) { possible.pb(i); } for (auto&ch : adj[i]) { if (ch != p) { dfs2(ch, i); } } } void solve() { cin >> n >> l; for (ll i = 1; i < n; i++) { ll u, v; cin >> u >> v; adj[u].pb(v), adj[v].pb(u); } dfs(l, 0); for (auto& ch : adj[l]) { subsz = sz[ch]; dfs2(ch, l); } sort(begin(possible), end(possible)); if(possible.size() > 0) { give(possible[0]); return; } give(-1); }
Editor is loading...
Leave a Comment