#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
struct DP {
int dp[2][2];
DP operator+( const DP &b ) const {
DP a = *this;
DP c;
for ( int s = 0; s < 2; s++ ) {
for ( int t = 0; t < 2; t++ )
c.dp[s][t] = INF;
}
for ( int sa = 0; sa < 2; sa++ ) {
for ( int ta = 0; ta < 2; ta++ ) {
for ( int sb = 0; sb < 2; sb++ ) {
for ( int tb = 0; tb < 2; tb++ ) {
if ( sb ^ ta == 1 )
continue;
c.dp[sa ^ tb][ta] = min( c.dp[sa ^ tb][ta], a.dp[sa][ta] + b.dp[sb][tb] );
}
}
}
}
return c;
}
};
const int MAX_N = 1e5;
bool isTurnedOn[MAX_N + 1];
DP minSwitches[MAX_N + 1];
vector <int> adj[MAX_N + 1];
void dfs( int u, int p ) {
for ( int s = 0; s < 2; s++ ) {
for ( int t = 0; t < 2; t++ )
minSwitches[u].dp[s][t] = (s ^ t == isTurnedOn[u] ? t : INF);
}
for ( int v: adj[u] ) {
if ( v == p )
continue;
dfs( v, u );
minSwitches[u] = minSwitches[u] + minSwitches[v];
}
/*printf( "%d\n", u );
printf( "%d %d\n", minSwitches[u].dp[0][0], minSwitches[u].dp[0][1] );
printf( "%d %d\n", minSwitches[u].dp[1][0], minSwitches[u].dp[1][1] );*/
}
int main() {
int n;
cin >> n;
for ( int i = 0; i < n - 1; i++ ) {
int u, v;
cin >> u >> v;
adj[u].push_back( v );
adj[v].push_back( u );
}
for ( int v = 1; v <= n; v++ )
cin >> isTurnedOn[v];
dfs( 1, 0 );
int ans = min( minSwitches[1].dp[0][0], minSwitches[1].dp[0][1] );
if ( ans <= n )
cout << ans;
else
cout << "impossible\n";
return 0;
}
Compilation message
xanadu.cpp: In member function 'DP DP::operator+(const DP&) const':
xanadu.cpp:23:38: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
23 | if ( sb ^ ta == 1 )
| ~~~^~~~
xanadu.cpp: In function 'void dfs(int, int)':
xanadu.cpp:43:46: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
43 | minSwitches[u].dp[s][t] = (s ^ t == isTurnedOn[u] ? t : INF);
| ~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2652 KB |
Output is correct |
5 |
Correct |
1 ms |
2904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2652 KB |
Output is correct |
5 |
Correct |
1 ms |
2904 KB |
Output is correct |
6 |
Correct |
2 ms |
2652 KB |
Output is correct |
7 |
Correct |
1 ms |
2652 KB |
Output is correct |
8 |
Correct |
1 ms |
2652 KB |
Output is correct |
9 |
Correct |
1 ms |
2652 KB |
Output is correct |
10 |
Correct |
1 ms |
2652 KB |
Output is correct |
11 |
Correct |
1 ms |
2648 KB |
Output is correct |
12 |
Correct |
1 ms |
2652 KB |
Output is correct |
13 |
Correct |
1 ms |
2652 KB |
Output is correct |
14 |
Correct |
1 ms |
2652 KB |
Output is correct |
15 |
Correct |
2 ms |
2652 KB |
Output is correct |
16 |
Correct |
1 ms |
2652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
72 ms |
21332 KB |
Output is correct |
2 |
Correct |
98 ms |
21028 KB |
Output is correct |
3 |
Correct |
73 ms |
21260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
21260 KB |
Output is correct |
2 |
Correct |
71 ms |
20940 KB |
Output is correct |
3 |
Correct |
73 ms |
21308 KB |
Output is correct |
4 |
Correct |
72 ms |
8136 KB |
Output is correct |
5 |
Correct |
71 ms |
8788 KB |
Output is correct |
6 |
Correct |
66 ms |
8824 KB |
Output is correct |
7 |
Correct |
1 ms |
2648 KB |
Output is correct |
8 |
Correct |
25 ms |
4776 KB |
Output is correct |
9 |
Correct |
65 ms |
8824 KB |
Output is correct |
10 |
Correct |
66 ms |
8816 KB |
Output is correct |
11 |
Correct |
65 ms |
9716 KB |
Output is correct |
12 |
Correct |
72 ms |
9888 KB |
Output is correct |
13 |
Correct |
65 ms |
8480 KB |
Output is correct |
14 |
Correct |
68 ms |
8788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2652 KB |
Output is correct |
5 |
Correct |
1 ms |
2904 KB |
Output is correct |
6 |
Correct |
2 ms |
2652 KB |
Output is correct |
7 |
Correct |
1 ms |
2652 KB |
Output is correct |
8 |
Correct |
1 ms |
2652 KB |
Output is correct |
9 |
Correct |
1 ms |
2652 KB |
Output is correct |
10 |
Correct |
1 ms |
2652 KB |
Output is correct |
11 |
Correct |
1 ms |
2648 KB |
Output is correct |
12 |
Correct |
1 ms |
2652 KB |
Output is correct |
13 |
Correct |
1 ms |
2652 KB |
Output is correct |
14 |
Correct |
1 ms |
2652 KB |
Output is correct |
15 |
Correct |
2 ms |
2652 KB |
Output is correct |
16 |
Correct |
1 ms |
2652 KB |
Output is correct |
17 |
Correct |
72 ms |
21332 KB |
Output is correct |
18 |
Correct |
98 ms |
21028 KB |
Output is correct |
19 |
Correct |
73 ms |
21260 KB |
Output is correct |
20 |
Correct |
73 ms |
21260 KB |
Output is correct |
21 |
Correct |
71 ms |
20940 KB |
Output is correct |
22 |
Correct |
73 ms |
21308 KB |
Output is correct |
23 |
Correct |
72 ms |
8136 KB |
Output is correct |
24 |
Correct |
71 ms |
8788 KB |
Output is correct |
25 |
Correct |
66 ms |
8824 KB |
Output is correct |
26 |
Correct |
1 ms |
2648 KB |
Output is correct |
27 |
Correct |
25 ms |
4776 KB |
Output is correct |
28 |
Correct |
65 ms |
8824 KB |
Output is correct |
29 |
Correct |
66 ms |
8816 KB |
Output is correct |
30 |
Correct |
65 ms |
9716 KB |
Output is correct |
31 |
Correct |
72 ms |
9888 KB |
Output is correct |
32 |
Correct |
65 ms |
8480 KB |
Output is correct |
33 |
Correct |
68 ms |
8788 KB |
Output is correct |
34 |
Correct |
1 ms |
2648 KB |
Output is correct |
35 |
Correct |
1 ms |
2652 KB |
Output is correct |
36 |
Correct |
1 ms |
2652 KB |
Output is correct |
37 |
Correct |
1 ms |
2904 KB |
Output is correct |
38 |
Correct |
1 ms |
2652 KB |
Output is correct |
39 |
Correct |
1 ms |
2652 KB |
Output is correct |
40 |
Correct |
1 ms |
2652 KB |
Output is correct |
41 |
Correct |
1 ms |
2648 KB |
Output is correct |
42 |
Correct |
1 ms |
2652 KB |
Output is correct |
43 |
Correct |
2 ms |
2652 KB |
Output is correct |
44 |
Correct |
1 ms |
2652 KB |
Output is correct |
45 |
Correct |
71 ms |
21244 KB |
Output is correct |
46 |
Correct |
74 ms |
21016 KB |
Output is correct |
47 |
Correct |
80 ms |
21252 KB |
Output is correct |
48 |
Correct |
59 ms |
8020 KB |
Output is correct |
49 |
Correct |
65 ms |
8744 KB |
Output is correct |
50 |
Correct |
66 ms |
8784 KB |
Output is correct |
51 |
Correct |
1 ms |
2648 KB |
Output is correct |
52 |
Correct |
22 ms |
4696 KB |
Output is correct |
53 |
Correct |
71 ms |
8784 KB |
Output is correct |
54 |
Correct |
75 ms |
9044 KB |
Output is correct |
55 |
Correct |
65 ms |
9812 KB |
Output is correct |
56 |
Correct |
71 ms |
9936 KB |
Output is correct |
57 |
Correct |
62 ms |
8528 KB |
Output is correct |
58 |
Correct |
65 ms |
8792 KB |
Output is correct |
59 |
Correct |
22 ms |
4688 KB |
Output is correct |
60 |
Correct |
65 ms |
8188 KB |
Output is correct |
61 |
Correct |
66 ms |
8740 KB |
Output is correct |
62 |
Correct |
65 ms |
8788 KB |
Output is correct |
63 |
Correct |
66 ms |
8944 KB |
Output is correct |
64 |
Correct |
74 ms |
9276 KB |
Output is correct |
65 |
Correct |
62 ms |
9300 KB |
Output is correct |
66 |
Correct |
63 ms |
9300 KB |
Output is correct |
67 |
Correct |
61 ms |
9160 KB |
Output is correct |
68 |
Correct |
64 ms |
9164 KB |
Output is correct |
69 |
Correct |
68 ms |
9200 KB |
Output is correct |
70 |
Correct |
59 ms |
9160 KB |
Output is correct |