#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
int n;
vector<bool> on;
int solve(int i,bool change,bool need){
if(i == n) return (need ? 1e9 : 0);
if(need) return solve(i+1,1,on[i]^change^1) + 1;
return solve(i+1,0,on[i]^change);
}
void solve(){
cin>>n;
vector<vector<int>> adj(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);
}
if(n <= 20){
int mask = 0;
for(int i=0;i<n;i++){
int x;
cin>>x;
if(!x) mask |= (1<<i);
}
queue<int> q;
vector<int> dep((1<<n),-1);
q.push(mask);
dep[mask] = 0;
while(q.size()){
int mask = q.front(); q.pop();
for(int i=0;i<n;i++){
int nmask = mask ^ (1<<i);
for(auto ch : adj[i]) nmask ^= (1<<ch);
if(~dep[nmask]) continue;
q.push(nmask);
dep[nmask] = dep[mask] + 1;
}
}
if(~dep[(1<<n)-1]) cout<<dep[(1<<n)-1]<<endl;
else cout<<"impossible"<<endl;
}
else {
on.resize(n);
for(int i=0;i<n;i++){
int x;cin>>x;
if(x) on[i] = 1;
}
int ans = solve(0,0,0);
if(ans >= 1e9) cout<<"impossible"<<endl;
else cout<<ans<<endl;
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
860 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
37 ms |
4816 KB |
Output is correct |
4 |
Correct |
70 ms |
5464 KB |
Output is correct |
5 |
Correct |
35 ms |
4952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
860 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
37 ms |
4816 KB |
Output is correct |
4 |
Correct |
70 ms |
5464 KB |
Output is correct |
5 |
Correct |
35 ms |
4952 KB |
Output is correct |
6 |
Correct |
6 ms |
856 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
34 ms |
4948 KB |
Output is correct |
9 |
Correct |
67 ms |
5360 KB |
Output is correct |
10 |
Correct |
34 ms |
4952 KB |
Output is correct |
11 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
6568 KB |
Output is correct |
2 |
Correct |
25 ms |
7516 KB |
Output is correct |
3 |
Correct |
29 ms |
7504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
6520 KB |
Output is correct |
2 |
Correct |
25 ms |
7432 KB |
Output is correct |
3 |
Correct |
28 ms |
7516 KB |
Output is correct |
4 |
Correct |
27 ms |
6740 KB |
Output is correct |
5 |
Correct |
35 ms |
7512 KB |
Output is correct |
6 |
Correct |
29 ms |
7504 KB |
Output is correct |
7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
860 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
37 ms |
4816 KB |
Output is correct |
4 |
Correct |
70 ms |
5464 KB |
Output is correct |
5 |
Correct |
35 ms |
4952 KB |
Output is correct |
6 |
Correct |
6 ms |
856 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
34 ms |
4948 KB |
Output is correct |
9 |
Correct |
67 ms |
5360 KB |
Output is correct |
10 |
Correct |
34 ms |
4952 KB |
Output is correct |
11 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |