TIMUS submission

 avatar
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