제출 #1249467

#제출 시각아이디문제언어결과실행 시간메모리
1249467antonnThe Xana coup (BOI21_xanadu)C++20
0 / 100
42 ms25668 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 7; int a[N], dp[N][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; dp[u][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 s = 0; s < 2; ++s) { if (s ^ val != a[v]) continue; nwmn[i ^ s] = min(nwmn[i ^ s], mn[i] + dp[v][s]); } } swap(nwmn, mn); } dp[u][0] = min(dp[u][0], mn[0]); dp[u][1] = min(dp[u][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) dp[i][0] = dp[i][1] = 1e9; dfs(1); if (dp[1][a[1]] == 1e9) { cout << "impossible\n"; return 0; } cout << dp[1][a[1]] << "\n"; return 0; }
#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...