Submission #1263632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263632		rtri	The Xana coup (BOI21_xanadu)	C++20	0 / 100	1096 ms	13892 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<int>> adj;
vector<int> cameras;

pair<int, int> dfs(int u, bool target, int p = -1) {
  bool is_leaf = true;
  for (int v : adj[u])
    if (v != p)
      is_leaf = false;
  if (is_leaf)
    return {target ^ cameras[u], target ^ cameras[u]};

  int ans = 1e9;
  int ansflip = 0;

  int zero_ans = 0;
  int zero_me = cameras[u];
  for (int v : adj[u])
    if (v != p) {
      auto [subans, flip] = dfs(v, 0, u);
      zero_ans += subans;
      zero_me += flip;
    }
  if (zero_me % 2 == target && zero_ans < ans) {
    ans = zero_ans;
    ansflip = 0;
  }

  int one_ans = 0;
  int one_me = cameras[u];
  for (int v : adj[u])
    if (v != p) {
      auto [subans, flip] = dfs(v, 1, u);
      one_ans += subans;
      one_me += flip;
    }
  if (one_me % 2 != target && one_ans + 1 < ans) {
    ans = one_ans + 1;
    ansflip = 1;
  }

  return {ans, ansflip};
}

int main() {
  cin >> n;

  adj.resize(n);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  cameras.resize(n);
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    cameras[i] = a;
  }

  int ans = dfs(0, 0).first;

  if (1e9 <= ans)
    cout << "impossible" << endl;
  else
    cout << ans << endl;

  return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 40
• Subtask 5: 0 / 30