제출 #398477

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
398477		model_code	The Xana coup (BOI21_xanadu)	C++17	100 / 100	143 ms	36744 KiB

xanadu

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000000;

int N, L[MAXN], dp[MAXN][2][2];
vector<int> e[MAXN];

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