제출 #1249480

#제출 시각아이디문제언어결과실행 시간메모리
1249480antonnThe Xana coup (BOI21_xanadu)C++20
100 / 100
61 ms24904 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 7; int a[N], dp[N][2][2]; vector<int> g[N]; void dfs(int u, int p = 0) { vector<int> kids; for (auto v : g[u]) { if (v != p) { dfs(v, u); kids.push_back(v); } } if (kids.size() == 0) { dp[u][0][0] = 0; dp[u][1][1] = 1; return; } for (int val = 0; val < 2; ++val) { vector<int> mn(2, 1e9); if (val == 1) { mn[1] = 1; } else { mn[0] = 0; } for (auto v : kids) { vector<int> nwmn(2, 1e9); for (int i = 0; i < 2; ++i) { for (int t = 0; t < 2; ++t) { for (int s = 0; s < 2; ++s) { if (s ^ val != a[v]) continue; nwmn[i ^ t] = min(nwmn[i ^ t], mn[i] + dp[v][t][s]); } } } swap(nwmn, mn); } dp[u][val][0] = min(dp[u][val][0], mn[0]); dp[u][val][1] = min(dp[u][val][1], mn[1]); } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; for (int i = 1; i < n; ++i) { int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); } for (int i = 1; i <= n; ++i) { cin >> a[i]; } for (int i = 1; i <= n; ++i) { for (int j = 0; j < 2; ++j) { for (int k = 0; k < 2; ++k) { dp[i][j][k] = 1e9; } } } dfs(1); int ans = 1e9; for (int t = 0; t < 2; ++t) ans = min(ans, dp[1][t][a[1]]); if (ans == 1e9) { cout << "impossible\n"; return 0; } cout << ans << "\n"; return 0; } /* 5 2 1 3 2 4 2 5 2 0 1 1 0 1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...