Submission #986296

#TimeUsernameProblemLanguageResultExecution timeMemory
986296dorjderemThe Xana coup (BOI21_xanadu)C++17
0 / 100
1088 ms7192 KiB
#include <iostream> #include <vector> #include <queue> #include <unordered_map> #include <bitset> using namespace std; #define ull unsigned long long int main() { int n; cin >> n; vector<vector<int>> adj(n); for (int i = 0; i < n - 1; ++i) { int a, b; cin >> a >> b; adj[a - 1].push_back(b - 1); adj[b - 1].push_back(a - 1); } int tree = 0; for (int i = 0; i < n; i++) { int a; cin >> a; if (a) tree |= (1 << i); } int ans = 1e9; for (int bit = 0; bit < (1 << n); bit++) { int a = tree; for (int i = 0; i < n; i++) { if (bit & (1 << i)) { a ^= (1 << i); for (int nxt : adj[i]) { a ^= (1 << nxt); } } } if (a == 0) { ans = min(ans, __builtin_popcount(bit)); } } if (ans < 1e9) cout << ans << endl; else cout << "IMPOSSIBLE"; 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...