Submission #861976

#	Time	Username	Problem	Language	Result	Execution time	Memory
861976		Trisanu_Das	The Xana coup (BOI21_xanadu)	C++17	100 / 100	81 ms	43688 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
 
int N, L[1000000], dp[1000000][2][2];
vector<int> e[1000000];
 
void dfs(int i = 0, int p = -1) {
  for (int s = 0; s < 2; s++) {
    dp[i][s][L[i] ^ s] = s;
    dp[i][s][L[i] ^ s ^ 1] = N + 1;
  }
  for (int j : e[i])
    if (j != p) {
      dfs(j, i);
      for (int s = 0; s < 2; s++) {
        int dp0 = dp[i][s][0], dp1 = dp[i][s][1];
        dp[i][s][0] = min(N + 1, min(dp0 + dp[j][0][s], dp1 + dp[j][1][s]));
        dp[i][s][1] = min(N + 1, min(dp0 + dp[j][1][s], dp1 + dp[j][0][s]));
      }
    }
}
 
int main() {
  cin >> N;
  int A, B;
  for (int i = 0; i < N - 1; i++) {
    cin >> A >> B;
    A--, B--;
    e[A].push_back(B);
    e[B].push_back(A);
  }
  for (int i = 0; i < N; i++) cin >> L[i];
  dfs();
  int r = min(dp[0][0][0], dp[0][1][0]);
  if (r > N) cout << "impossible\n";
  else cout << r << "\n";
}

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