Submission #574284

#TimeUsernameProblemLanguageResultExecution timeMemory
574284moday_morningThe Xana coup (BOI21_xanadu)C++17
5 / 100
1093 ms15968 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int INF = 1e9, N = 1e5 + 5; vector <vector <int> > a; int minn = INF, n; vector <int> v, point; void checker (int validator) { if (validator == n) { vector <int> p = point; for (auto i : v) { p[i] = !p[i]; for (auto pos : a[i]) { p[pos] = !p[pos]; } if (all_of(p.begin(), p.end(), [&](int z) { return z == 0; })) { minn = min(minn, (int)v.size()); } } } else { v.push_back(validator); checker(validator + 1); v.pop_back(); checker(validator + 1); } } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; a.resize(n); for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; u--; v--; a[u].push_back(v); a[v].push_back(u); } point.resize(n); for (int i = 0; i < n; i++) { cin >> point[i]; } checker(0); if (minn >= INF) { cout << "impossible\n"; } else { cout << minn << "\n"; } }
#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...