#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N = 1e5+50, mod = 998244353, K = 31;
int dp[N][2][2][2];
int n;
int A[N];
vector<int>gr[N];
int x,y;
///// chartuli, dawerili, shvilebi;
inline void Min(int &x,int val){
x = min(x,val);
}
void dfs(int x,int p){
int cur = A[x];
if(x != 1 && gr[x].size() == 1){
dp[x][cur][0][0] = 0;
dp[x][1-cur][1][0] = 1;
dp[x][cur][0][1] = 0;
dp[x][1-cur][1][1] = 1;
return ;
}
dp[x][cur][0][0] = 0;
dp[x][cur][0][1] = 0;
for(auto to : gr[x]){
if(to == p) continue;
dfs(to,x);
int cur_dp[2][2][2];
for(int j = 0; j < 2; j++){
for(int t = 0; t < 2; t++){
for(int k = 0; k < 2; k++){
cur_dp[j][t][k] = 1e9;
}
}
}
for(int chart = 0; chart < 2; chart++){
//for(int daw = 0; daw < 2; daw++){
int daw = 0;
for(int shvi = 0; shvi < 2; shvi++){
if(dp[x][chart][daw][shvi] >= 1e9) continue;
int res = dp[x][chart][daw][shvi];
Min(cur_dp[chart][daw][shvi], res+dp[to][shvi][0][0]);
Min(cur_dp[1-chart][daw][shvi], res+dp[to][shvi][1][0]);
}
//}
}
for(int j = 0; j < 2; j++){
for(int t = 0; t < 2; t++){
for(int k = 0; k < 2; k++){
dp[x][j][t][k] = cur_dp[j][t][k];
}
}
}
}
Min(dp[x][0][1][0], dp[x][1][0][1]+1);
Min(dp[x][1][1][0], dp[x][0][0][1]+1);
}
inline void test_case(){
cin >> n;
for(int i = 1; i < n; i++){
cin >> x >> y;
gr[x].pb(y);
gr[y].pb(x);
}
for(int i = 1; i <= n; i++){
cin >> A[i];
}
for(int i = 1; i <= n; i++){
for(int j = 0; j < 2; j++){
for(int t = 0; t < 2; t++){
for(int k = 0; k < 2; k++){
dp[i][j][t][k] = 1e9;
}
}
}
}
dfs(1,0);
int answer = min(dp[1][0][0][0],dp[1][0][1][0]);
if(answer >= 1e9){
cout << "impossible" << endl;
} else {
cout << answer << endl;
}
}
main(){
ios::sync_with_stdio(0);
int T = 1;
//cin >> T;
for(int i = 1; i <= T; i++){
test_case();
}
}
Compilation message
xanadu.cpp:106:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
106 | main(){
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2680 KB |
Output is correct |
2 |
Correct |
2 ms |
2692 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2680 KB |
Output is correct |
2 |
Correct |
2 ms |
2692 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2676 KB |
Output is correct |
6 |
Correct |
2 ms |
2636 KB |
Output is correct |
7 |
Correct |
2 ms |
2636 KB |
Output is correct |
8 |
Correct |
2 ms |
2636 KB |
Output is correct |
9 |
Correct |
3 ms |
2636 KB |
Output is correct |
10 |
Correct |
2 ms |
2636 KB |
Output is correct |
11 |
Correct |
2 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2636 KB |
Output is correct |
13 |
Correct |
2 ms |
2636 KB |
Output is correct |
14 |
Correct |
2 ms |
2636 KB |
Output is correct |
15 |
Correct |
2 ms |
2636 KB |
Output is correct |
16 |
Correct |
2 ms |
2636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
88 ms |
24544 KB |
Output is correct |
2 |
Correct |
78 ms |
24356 KB |
Output is correct |
3 |
Correct |
75 ms |
24740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
72 ms |
24536 KB |
Output is correct |
2 |
Correct |
76 ms |
24312 KB |
Output is correct |
3 |
Correct |
94 ms |
24720 KB |
Output is correct |
4 |
Correct |
87 ms |
9764 KB |
Output is correct |
5 |
Correct |
81 ms |
10564 KB |
Output is correct |
6 |
Correct |
71 ms |
10564 KB |
Output is correct |
7 |
Correct |
3 ms |
2636 KB |
Output is correct |
8 |
Correct |
23 ms |
5412 KB |
Output is correct |
9 |
Correct |
73 ms |
10608 KB |
Output is correct |
10 |
Correct |
120 ms |
10820 KB |
Output is correct |
11 |
Correct |
102 ms |
11588 KB |
Output is correct |
12 |
Correct |
75 ms |
11860 KB |
Output is correct |
13 |
Correct |
65 ms |
10076 KB |
Output is correct |
14 |
Correct |
75 ms |
10692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2680 KB |
Output is correct |
2 |
Correct |
2 ms |
2692 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2676 KB |
Output is correct |
6 |
Correct |
2 ms |
2636 KB |
Output is correct |
7 |
Correct |
2 ms |
2636 KB |
Output is correct |
8 |
Correct |
2 ms |
2636 KB |
Output is correct |
9 |
Correct |
3 ms |
2636 KB |
Output is correct |
10 |
Correct |
2 ms |
2636 KB |
Output is correct |
11 |
Correct |
2 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2636 KB |
Output is correct |
13 |
Correct |
2 ms |
2636 KB |
Output is correct |
14 |
Correct |
2 ms |
2636 KB |
Output is correct |
15 |
Correct |
2 ms |
2636 KB |
Output is correct |
16 |
Correct |
2 ms |
2636 KB |
Output is correct |
17 |
Correct |
88 ms |
24544 KB |
Output is correct |
18 |
Correct |
78 ms |
24356 KB |
Output is correct |
19 |
Correct |
75 ms |
24740 KB |
Output is correct |
20 |
Correct |
72 ms |
24536 KB |
Output is correct |
21 |
Correct |
76 ms |
24312 KB |
Output is correct |
22 |
Correct |
94 ms |
24720 KB |
Output is correct |
23 |
Correct |
87 ms |
9764 KB |
Output is correct |
24 |
Correct |
81 ms |
10564 KB |
Output is correct |
25 |
Correct |
71 ms |
10564 KB |
Output is correct |
26 |
Correct |
3 ms |
2636 KB |
Output is correct |
27 |
Correct |
23 ms |
5412 KB |
Output is correct |
28 |
Correct |
73 ms |
10608 KB |
Output is correct |
29 |
Correct |
120 ms |
10820 KB |
Output is correct |
30 |
Correct |
102 ms |
11588 KB |
Output is correct |
31 |
Correct |
75 ms |
11860 KB |
Output is correct |
32 |
Correct |
65 ms |
10076 KB |
Output is correct |
33 |
Correct |
75 ms |
10692 KB |
Output is correct |
34 |
Correct |
2 ms |
2636 KB |
Output is correct |
35 |
Correct |
2 ms |
2636 KB |
Output is correct |
36 |
Correct |
2 ms |
2636 KB |
Output is correct |
37 |
Correct |
2 ms |
2636 KB |
Output is correct |
38 |
Correct |
2 ms |
2636 KB |
Output is correct |
39 |
Correct |
3 ms |
2636 KB |
Output is correct |
40 |
Correct |
3 ms |
2684 KB |
Output is correct |
41 |
Correct |
3 ms |
2636 KB |
Output is correct |
42 |
Correct |
2 ms |
2636 KB |
Output is correct |
43 |
Correct |
3 ms |
2636 KB |
Output is correct |
44 |
Correct |
2 ms |
2636 KB |
Output is correct |
45 |
Correct |
79 ms |
24596 KB |
Output is correct |
46 |
Correct |
73 ms |
24260 KB |
Output is correct |
47 |
Correct |
80 ms |
24692 KB |
Output is correct |
48 |
Correct |
85 ms |
9760 KB |
Output is correct |
49 |
Correct |
95 ms |
10528 KB |
Output is correct |
50 |
Correct |
87 ms |
10548 KB |
Output is correct |
51 |
Correct |
3 ms |
2636 KB |
Output is correct |
52 |
Correct |
20 ms |
5424 KB |
Output is correct |
53 |
Correct |
72 ms |
10564 KB |
Output is correct |
54 |
Correct |
86 ms |
10796 KB |
Output is correct |
55 |
Correct |
87 ms |
11604 KB |
Output is correct |
56 |
Correct |
83 ms |
11912 KB |
Output is correct |
57 |
Correct |
72 ms |
10120 KB |
Output is correct |
58 |
Correct |
71 ms |
10564 KB |
Output is correct |
59 |
Correct |
23 ms |
5324 KB |
Output is correct |
60 |
Correct |
70 ms |
9864 KB |
Output is correct |
61 |
Correct |
90 ms |
10532 KB |
Output is correct |
62 |
Correct |
86 ms |
10704 KB |
Output is correct |
63 |
Correct |
97 ms |
10768 KB |
Output is correct |
64 |
Correct |
81 ms |
10832 KB |
Output is correct |
65 |
Correct |
59 ms |
11080 KB |
Output is correct |
66 |
Correct |
68 ms |
11104 KB |
Output is correct |
67 |
Correct |
57 ms |
11072 KB |
Output is correct |
68 |
Correct |
69 ms |
11016 KB |
Output is correct |
69 |
Correct |
55 ms |
11000 KB |
Output is correct |
70 |
Correct |
60 ms |
11052 KB |
Output is correct |