Submission #1263415

#TimeUsernameProblemLanguageResultExecution timeMemory
1263415rtriThe Xana coup (BOI21_xanadu)C++20
0 / 100
1096 ms13892 KiB
#include <bits/stdc++.h> using namespace std; int n; vector<vector<int>> adj; vector<int> cameras; bool happy = true; pair<int, int> dfs(int u, bool target, int p = -1) { bool is_leaf = true; for (int v : adj[u]) if (v != p) is_leaf = false; if (is_leaf) return {target ^ cameras[u], target ^ cameras[u]}; int ans = 1e9; int ansflip = 0; int zero_ans = 0; int zero_me = cameras[u]; for (int v : adj[u]) if (v != p) { auto [subans, flip] = dfs(v, 0, u); zero_ans += subans; zero_me += flip; } if (zero_me % 2 == target && zero_ans < ans) { ans = zero_ans; ansflip = 0; } int one_ans = 0; int one_me = cameras[u]; for (int v : adj[u]) if (v != p) { auto [subans, flip] = dfs(v, 1, u); one_ans += subans; one_me += flip; } if (one_me % 2 != target && one_ans < ans) { ans = one_ans + 1; ansflip = 1; } if (ans == 1e9) happy = false; return {ans, ansflip}; } int main() { cin >> n; adj.resize(n); for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; a--; b--; adj[a].push_back(b); adj[b].push_back(a); } cameras.resize(n); for (int i = 0; i < n; i++) { int a; cin >> a; cameras[i] = a; } int ans = dfs(0, 0).first; if (!happy) cout << "impossible" << endl; else cout << ans << endl; 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...