# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1056753 | kachim2 | The Xana coup (BOI21_xanadu) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
vector<vector<long>> tree;
long N; long bst = LONG_MAX;
void x(vector<bool> lit, long n, long cnt){
bool gud = 0;
for(long i = 1; i <= N; i++)
if(lit[i]) gud = 1;
if(!gud){
bst = min(bst, cnt);
}
if(n==N+1) return;
x(lit, n+1, cnt);
lit[n] = !lit[n] ;
for(auto i : tree[n]) lit[i] = !lit[i];
x(lit, n+1, cnt+1);
}
int main(){
long n;
cin >> n;
N=n;
tree.resize(n+1);
vector<bool> lit(n+1);
for(long i = 0; i < n-1; i++){
long a, b;
cin >> a >> b;
tree[a].push_back(b);
tree[b].push_back(a);
}
for(long i = 1; i <= n; i++){
long x;cin >> x; lit[i] = x;
}
x(lit, 1, 0);
if(bst == long_MAX)
cout << "imposible";
else
cout << bst;
}