Submission #797358

#	Time	Username	Problem	Language	Result	Execution time	Memory
797358		tch1cherin	The Xana coup (BOI21_xanadu)	C++17	100 / 100	65 ms	18428 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
 
const int N = 100000;
vector<int> g[N];
int dp[N][2][2], a[N];
 
void DFS(int u = 0, int p = -1) {
  for (int v : g[u]) {
    if (v != p) {
      DFS(v, u);
    }
  }
  for (int par = 0; par < 2; par++) {
    for (int cur = 0; cur < 2; cur++) {
      int ans[2] = {N + 1, N + 1};
      ans[par ^ cur] = cur;
      for (int v : g[u]) {
        if (v == p) {
          continue;
        }
        int new_ans[2] = {N + 1, N + 1};
        for (int c = 0; c < 2; c++) {
          for (int d = 0; d < 2; d++) {
            new_ans[d ^ c] = min(new_ans[d ^ c], ans[d] + dp[v][cur][c]);   
          }
        }
        ans[0] = new_ans[0];
        ans[1] = new_ans[1];
      }
      dp[u][par][cur] = ans[a[u]]; 
    }
  } 
}
 
void solve() {
  int n;
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  DFS();
  int ans = min(dp[0][0][0], dp[0][0][1]);
  if (ans == N + 1) {
    cout << "impossible\n";
  } else {
    cout << ans << "\n";
  }
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}

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