Submission #519873

#	Time	Username	Problem	Language	Result	Execution time	Memory
519873		erke	The Xana coup (BOI21_xanadu)	C++11	100 / 100	78 ms	15324 KiB

xanadu

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

typedef long long ll;

const int N = 100005;
const int oo = 1e9;

vector<int> adj[N];
int color[N], dp[N][2][2];

template<typename T>
void chmin(T &a, T b) {
  if (a > b) a = b;
}

void dfs(int i, int p) {
  if (color[i] == 0) {
    dp[i][0][0] = 0;
    dp[i][1][1] = 1;
  }
  else if (color[i] == 1) {
    dp[i][1][0] = 0;
    dp[i][0][1] = 1;
  }
  for (auto &j : adj[i]) {
    if (j == p) continue;
    dfs(j, i);
    array<array<int,2>,2> cur_dp;
    cur_dp[0][0] = min(dp[i][0][0] + dp[j][0][0], dp[i][1][0] + dp[j][0][1]);
    cur_dp[0][1] = min(dp[i][0][1] + dp[j][1][0], dp[i][1][1] + dp[j][1][1]);
    cur_dp[1][0] = min(dp[i][0][0] + dp[j][0][1], dp[i][1][0] + dp[j][0][0]);
    cur_dp[1][1] = min(dp[i][0][1] + dp[j][1][1], dp[i][1][1] + dp[j][1][0]);
    for (int k = 0; k <= 1; k++)
    for (int l = 0; l <= 1; l++) {
      if (cur_dp[k][l] >= oo) cur_dp[k][l] = oo;
      dp[i][k][l] = cur_dp[k][l];
    }
  }
  /*cerr << "i = " << i << '\n';
  for (int k = 0; k <= 1; k++)
  for (int l = 0; l <= 1; l++) {
    if (dp[i][k][l] >= oo) {
      cerr << "-" << " \n"[l == 1];
    }
    else cerr << dp[i][k][l] << " \n"[l == 1];
  }*/
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  int n; cin >> n;
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  for (int i = 1; i <= n; i++) {
    cin >> color[i];
  }
  for (int i = 0; i < N; i++)
  for (int j = 0; j < 2; j++)
  for (int k = 0; k < 2; k++) {
    dp[i][j][k] = oo;
  }
  dfs(1, -1);
  int ans = min(dp[1][0][0], dp[1][0][1]);
  if (ans >= oo) cout << "impossible" << '\n';
  else cout << ans << '\n';
}

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