#include <bits/stdc++.h>
using namespace std ;
const int MAX = 1e5 + 10 ;
int arr[MAX] ;
int n ;
vector< vector<int> >adj(MAX) ;
int vis[MAX][2] ;
long long dp[MAX][2][2] ;
void dfs(int node , int par , bool toggle)
{
if(vis[node][toggle])
return ;
vis[node][toggle] = 1 ;
dp[node][toggle][0] = dp[node][toggle][1] = n+1 ;
int cur = arr[node] ^ toggle ;
long long sum0 = 0 , sum1 = 1 ;
vector<long long>v[2] ;
for(auto &child : adj[node])
{
if(child == par)
continue ;
dfs(child , node , 0) , dfs(child , node , 1) ;
sum0 += dp[child][0][0] , sum1 += dp[child][1][0] ;
v[0].push_back(dp[child][0][1] - dp[child][0][0]) ;
v[1].push_back(dp[child][1][1] - dp[child][1][0]) ;
}
sort(v[0].begin() , v[0].end()) ;
sort(v[1].begin() , v[1].end()) ;
if((!cur))
dp[node][toggle][0] = sum0 ;
else
dp[node][toggle][1] = sum1 ;
for(int i = 0 ; i < v[0].size() ; ++i)
{
sum0 += v[0][i] ;
if((i+1) % 2 == cur)
dp[node][toggle][0] = min(dp[node][toggle][0] , sum0) ;
}
for(int i = 0 ; i < v[1].size() ; ++i)
{
sum1 += v[1][i] ;
if((i+1) % 2 != cur)
dp[node][toggle][1] = min(dp[node][toggle][1] , sum1) ;
}
}
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>n ;
for(int i = 0 ; i < n-1 ; ++i)
{
int x , y ;
cin>>x>>y ;
adj[x].push_back(y) ;
adj[y].push_back(x) ;
}
for(int i = 1 ; i <= n ; ++i)
cin>>arr[i] ;
dfs(1 , -1 , 0) ;
long long ans = min(dp[1][0][0] , dp[1][0][1]) ;
if(ans > n)
cout<<"impossible\n" ;
else
cout<<ans<<"\n" ;
return 0 ;
}
Compilation message
xanadu.cpp: In function 'void dfs(int, int, bool)':
xanadu.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i = 0 ; i < v[0].size() ; ++i)
| ~~^~~~~~~~~~~~~
xanadu.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i = 0 ; i < v[1].size() ; ++i)
| ~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2696 KB |
Output is correct |
4 |
Correct |
2 ms |
2704 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2696 KB |
Output is correct |
4 |
Correct |
2 ms |
2704 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
1 ms |
2644 KB |
Output is correct |
7 |
Correct |
1 ms |
2700 KB |
Output is correct |
8 |
Correct |
1 ms |
2644 KB |
Output is correct |
9 |
Correct |
1 ms |
2644 KB |
Output is correct |
10 |
Correct |
1 ms |
2644 KB |
Output is correct |
11 |
Correct |
1 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2700 KB |
Output is correct |
13 |
Correct |
1 ms |
2644 KB |
Output is correct |
14 |
Correct |
1 ms |
2696 KB |
Output is correct |
15 |
Correct |
1 ms |
2644 KB |
Output is correct |
16 |
Correct |
1 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
30016 KB |
Output is correct |
2 |
Correct |
52 ms |
29704 KB |
Output is correct |
3 |
Correct |
54 ms |
30176 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
29976 KB |
Output is correct |
2 |
Correct |
52 ms |
29748 KB |
Output is correct |
3 |
Correct |
52 ms |
30192 KB |
Output is correct |
4 |
Correct |
42 ms |
10488 KB |
Output is correct |
5 |
Correct |
45 ms |
11176 KB |
Output is correct |
6 |
Correct |
49 ms |
11440 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
16 ms |
5716 KB |
Output is correct |
9 |
Correct |
50 ms |
11492 KB |
Output is correct |
10 |
Correct |
48 ms |
11660 KB |
Output is correct |
11 |
Correct |
50 ms |
13048 KB |
Output is correct |
12 |
Correct |
48 ms |
13364 KB |
Output is correct |
13 |
Correct |
50 ms |
10888 KB |
Output is correct |
14 |
Correct |
46 ms |
11360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2696 KB |
Output is correct |
4 |
Correct |
2 ms |
2704 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
1 ms |
2644 KB |
Output is correct |
7 |
Correct |
1 ms |
2700 KB |
Output is correct |
8 |
Correct |
1 ms |
2644 KB |
Output is correct |
9 |
Correct |
1 ms |
2644 KB |
Output is correct |
10 |
Correct |
1 ms |
2644 KB |
Output is correct |
11 |
Correct |
1 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2700 KB |
Output is correct |
13 |
Correct |
1 ms |
2644 KB |
Output is correct |
14 |
Correct |
1 ms |
2696 KB |
Output is correct |
15 |
Correct |
1 ms |
2644 KB |
Output is correct |
16 |
Correct |
1 ms |
2644 KB |
Output is correct |
17 |
Correct |
50 ms |
30016 KB |
Output is correct |
18 |
Correct |
52 ms |
29704 KB |
Output is correct |
19 |
Correct |
54 ms |
30176 KB |
Output is correct |
20 |
Correct |
51 ms |
29976 KB |
Output is correct |
21 |
Correct |
52 ms |
29748 KB |
Output is correct |
22 |
Correct |
52 ms |
30192 KB |
Output is correct |
23 |
Correct |
42 ms |
10488 KB |
Output is correct |
24 |
Correct |
45 ms |
11176 KB |
Output is correct |
25 |
Correct |
49 ms |
11440 KB |
Output is correct |
26 |
Correct |
1 ms |
2644 KB |
Output is correct |
27 |
Correct |
16 ms |
5716 KB |
Output is correct |
28 |
Correct |
50 ms |
11492 KB |
Output is correct |
29 |
Correct |
48 ms |
11660 KB |
Output is correct |
30 |
Correct |
50 ms |
13048 KB |
Output is correct |
31 |
Correct |
48 ms |
13364 KB |
Output is correct |
32 |
Correct |
50 ms |
10888 KB |
Output is correct |
33 |
Correct |
46 ms |
11360 KB |
Output is correct |
34 |
Correct |
1 ms |
2644 KB |
Output is correct |
35 |
Correct |
2 ms |
2772 KB |
Output is correct |
36 |
Correct |
1 ms |
2644 KB |
Output is correct |
37 |
Correct |
2 ms |
2644 KB |
Output is correct |
38 |
Correct |
1 ms |
2700 KB |
Output is correct |
39 |
Correct |
1 ms |
2700 KB |
Output is correct |
40 |
Correct |
1 ms |
2644 KB |
Output is correct |
41 |
Correct |
1 ms |
2644 KB |
Output is correct |
42 |
Correct |
2 ms |
2660 KB |
Output is correct |
43 |
Correct |
1 ms |
2644 KB |
Output is correct |
44 |
Correct |
1 ms |
2644 KB |
Output is correct |
45 |
Correct |
53 ms |
30100 KB |
Output is correct |
46 |
Correct |
50 ms |
29696 KB |
Output is correct |
47 |
Correct |
51 ms |
30156 KB |
Output is correct |
48 |
Correct |
42 ms |
10424 KB |
Output is correct |
49 |
Correct |
56 ms |
11216 KB |
Output is correct |
50 |
Correct |
47 ms |
11392 KB |
Output is correct |
51 |
Correct |
2 ms |
2644 KB |
Output is correct |
52 |
Correct |
16 ms |
5716 KB |
Output is correct |
53 |
Correct |
45 ms |
11480 KB |
Output is correct |
54 |
Correct |
48 ms |
11672 KB |
Output is correct |
55 |
Correct |
61 ms |
13048 KB |
Output is correct |
56 |
Correct |
47 ms |
13392 KB |
Output is correct |
57 |
Correct |
45 ms |
10816 KB |
Output is correct |
58 |
Correct |
46 ms |
11476 KB |
Output is correct |
59 |
Correct |
16 ms |
5684 KB |
Output is correct |
60 |
Correct |
42 ms |
10584 KB |
Output is correct |
61 |
Correct |
51 ms |
11384 KB |
Output is correct |
62 |
Correct |
50 ms |
11580 KB |
Output is correct |
63 |
Correct |
48 ms |
11648 KB |
Output is correct |
64 |
Correct |
48 ms |
11632 KB |
Output is correct |
65 |
Correct |
41 ms |
12004 KB |
Output is correct |
66 |
Correct |
45 ms |
11940 KB |
Output is correct |
67 |
Correct |
44 ms |
14740 KB |
Output is correct |
68 |
Correct |
38 ms |
14776 KB |
Output is correct |
69 |
Correct |
39 ms |
14752 KB |
Output is correct |
70 |
Correct |
40 ms |
14820 KB |
Output is correct |