#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define sz(v) (int)v.size()
#define FOR(i,a,b) for(int i=a; i<b; i++)
void ckmin(int &x, int y){x=min(x,y);}
void IO() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
//------------------------------------------------//
const int MX=1e5+10;
const int INF=1e9;
int N;
vi adj[MX],a(MX);
int memo[MX][2][2];
int solve(int u, int p, int f, int ff){
int &ind=memo[u][f][ff];
if(ind!=-1) return ind;
int st=a[u]; if(f) st=1-st; if(ff) st=1-st;
int ans=INF,n=sz(adj[u])-(u!=1);
FOR(m,0,((1)<<(n))) if(((__builtin_popcount(m))&1)==st){
int cur=ff,idx=0;
for(int v: adj[u]) if(v!=p){
int nf=(((m)>>(idx))&1);
cur+=solve(v,u,ff,nf);
if(cur>INF) cur=INF;
idx++;
}
ckmin(ans,cur);
}
return ind=ans;
}
int main(){
IO();
cin>>N;
FOR(i,0,N-1){
int u,v; cin>>u>>v;
adj[u].pb(v);
adj[v].pb(u);
}
FOR(i,1,N+1) cin>>a[i];
memset(memo,-1,sizeof(memo));
int ans=min(solve(1,1,0,0),solve(1,1,0,1));
if(ans==INF) cout << "impossible" << endl;
else cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4556 KB |
Output is correct |
2 |
Correct |
3 ms |
4556 KB |
Output is correct |
3 |
Correct |
3 ms |
4556 KB |
Output is correct |
4 |
Correct |
3 ms |
4592 KB |
Output is correct |
5 |
Correct |
3 ms |
4556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4556 KB |
Output is correct |
2 |
Correct |
3 ms |
4556 KB |
Output is correct |
3 |
Correct |
3 ms |
4556 KB |
Output is correct |
4 |
Correct |
3 ms |
4592 KB |
Output is correct |
5 |
Correct |
3 ms |
4556 KB |
Output is correct |
6 |
Correct |
3 ms |
4556 KB |
Output is correct |
7 |
Correct |
3 ms |
4556 KB |
Output is correct |
8 |
Correct |
3 ms |
4556 KB |
Output is correct |
9 |
Correct |
3 ms |
4556 KB |
Output is correct |
10 |
Correct |
3 ms |
4556 KB |
Output is correct |
11 |
Correct |
3 ms |
4556 KB |
Output is correct |
12 |
Correct |
3 ms |
4556 KB |
Output is correct |
13 |
Correct |
3 ms |
4556 KB |
Output is correct |
14 |
Correct |
3 ms |
4600 KB |
Output is correct |
15 |
Incorrect |
3 ms |
4592 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
116 ms |
18560 KB |
Output is correct |
2 |
Correct |
119 ms |
18372 KB |
Output is correct |
3 |
Correct |
119 ms |
18600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
124 ms |
18596 KB |
Output is correct |
2 |
Correct |
118 ms |
18428 KB |
Output is correct |
3 |
Correct |
118 ms |
18660 KB |
Output is correct |
4 |
Correct |
110 ms |
7364 KB |
Output is correct |
5 |
Correct |
131 ms |
9044 KB |
Output is correct |
6 |
Correct |
128 ms |
9000 KB |
Output is correct |
7 |
Correct |
3 ms |
4556 KB |
Output is correct |
8 |
Correct |
40 ms |
6060 KB |
Output is correct |
9 |
Correct |
123 ms |
9064 KB |
Output is correct |
10 |
Correct |
133 ms |
9300 KB |
Output is correct |
11 |
Correct |
123 ms |
9796 KB |
Output is correct |
12 |
Correct |
128 ms |
10004 KB |
Output is correct |
13 |
Correct |
114 ms |
8716 KB |
Output is correct |
14 |
Correct |
125 ms |
9072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4556 KB |
Output is correct |
2 |
Correct |
3 ms |
4556 KB |
Output is correct |
3 |
Correct |
3 ms |
4556 KB |
Output is correct |
4 |
Correct |
3 ms |
4592 KB |
Output is correct |
5 |
Correct |
3 ms |
4556 KB |
Output is correct |
6 |
Correct |
3 ms |
4556 KB |
Output is correct |
7 |
Correct |
3 ms |
4556 KB |
Output is correct |
8 |
Correct |
3 ms |
4556 KB |
Output is correct |
9 |
Correct |
3 ms |
4556 KB |
Output is correct |
10 |
Correct |
3 ms |
4556 KB |
Output is correct |
11 |
Correct |
3 ms |
4556 KB |
Output is correct |
12 |
Correct |
3 ms |
4556 KB |
Output is correct |
13 |
Correct |
3 ms |
4556 KB |
Output is correct |
14 |
Correct |
3 ms |
4600 KB |
Output is correct |
15 |
Incorrect |
3 ms |
4592 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |