#include <bits/stdc++.h>
#define ar array
using namespace std;
using ll = long long;
const ll INF = 1e9;
const int mxN = 1e5;
vector<int> g[mxN];
int a[mxN];
// 0b(pressed)(state)
ar<ll, 4> solve(int cur, int prv) {
int kid_cnt = 0;
for (int nxt : g[cur]) {
if (nxt == prv) continue;
++kid_cnt;
}
if (!kid_cnt) {
ar<ll, 4> ret {INF, INF, INF, INF};
if (a[cur]) {
ret[0b01] = 0;
ret[0b10] = 1;
} else {
ret[0b00] = 0;
ret[0b11] = 1;
}
/*
cerr << cur << '\n';
cerr << kid_cnt << '\n';
for (int s = 0; s < 1<<2; ++s)
cerr << bitset<2>(s) << ' ' << ret[s] << '\n';
cerr << '\n'; */
return ret;
}
vector<ll> kid_costs[4];
for (int nxt : g[cur]) {
if (nxt == prv) continue;
auto r = solve(nxt, cur);
for (int s = 0; s < 1<<2; ++s)
kid_costs[s].push_back(r[s]);
}
/*
for (int s = 0; s < 1<<2; ++s) {
cerr << bitset<2>(s) << ": ";
for (int i = 0; i < kid_cnt; ++i)
cerr << kid_costs[s][i] << ' ';
cerr << '\n';
} // */
ar<ll, 4> ret {INF, INF, INF, INF};
// not pressed
// can only take 0b00 or 0b10
vector<int> idxs(kid_cnt);
iota(idxs.begin(), idxs.end(), 0);
sort(idxs.begin(), idxs.end(), [&](int i, int j) {
return kid_costs[0b010][i]-kid_costs[0b00][i]
< kid_costs[0b010][j]-kid_costs[0b00][j];
});
ll s0x = 0;
for (int i = 0; i < kid_cnt; ++i)
s0x += kid_costs[0b00][i];
ret[0b00 ^ a[cur]] = min(ret[0b00 ^ a[cur]], s0x);
for (int swp = 0; swp < kid_cnt; ++swp) {
s0x -= kid_costs[0b00][idxs[swp]];
s0x += kid_costs[0b10][idxs[swp]];
int msk = 0b00 ^ (a[cur]^((swp+1)&1));
//cerr << "s0x " << bitset<2>(msk) << ' ' << swp << ' ' << s0x << '\n';
ret[msk] = min(ret[msk], s0x);
}
// pressed
// can only take 0b01 or 0b11
sort(idxs.begin(), idxs.end(), [&](int i, int j) {
return kid_costs[0b011][i]-kid_costs[0b01][i]
< kid_costs[0b011][j]-kid_costs[0b01][j];
});
ll s1x = 1;
for (int i = 0; i < kid_cnt; ++i)
s1x += kid_costs[0b01][i];
ret[0b11 ^ a[cur]] = min(ret[0b11 ^ a[cur]], s1x);
for (int swp = 0; swp < kid_cnt; ++swp) {
s1x -= kid_costs[0b01][idxs[swp]];
s1x += kid_costs[0b11][idxs[swp]];
int msk = 0b11 ^ (a[cur]^((swp+1)&1));
//cerr << "s1x " << bitset<2>(msk) << ' ' << swp << ' ' << s1x << '\n';
ret[msk] = min(ret[msk], s1x);
}
//cerr << cur << '\n';
//cerr << kid_cnt << '\n';
/*
for (int s = 0; s < 1<<2; ++s)
cerr << bitset<2>(s) << ' ' << ret[s] << '\n';
cerr << '\n'; // */
return ret;
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);
int n; cin >> n;
for (int nn = 0; nn < n-1; ++nn) {
int i, j; cin >> i >> j; --i, --j;
g[i].push_back(j);
g[j].push_back(i);
}
for (int i = 0; i < n; ++i)
cin >> a[i];
auto ans_ar = solve(0, -1);
ll ans = min(ans_ar[0b00], ans_ar[0b10]);
if (ans > n) {
cout << "impossible\n";
return 0;
}
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2672 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2672 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
2 ms |
2672 KB |
Output is correct |
7 |
Correct |
2 ms |
2668 KB |
Output is correct |
8 |
Correct |
2 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2672 KB |
Output is correct |
10 |
Correct |
2 ms |
2636 KB |
Output is correct |
11 |
Correct |
3 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 |
3 ms |
2676 KB |
Output is correct |
16 |
Correct |
2 ms |
2668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
32360 KB |
Output is correct |
2 |
Correct |
90 ms |
31956 KB |
Output is correct |
3 |
Correct |
84 ms |
32560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
83 ms |
32376 KB |
Output is correct |
2 |
Correct |
81 ms |
31940 KB |
Output is correct |
3 |
Correct |
85 ms |
32472 KB |
Output is correct |
4 |
Correct |
66 ms |
7048 KB |
Output is correct |
5 |
Correct |
77 ms |
7436 KB |
Output is correct |
6 |
Correct |
71 ms |
7492 KB |
Output is correct |
7 |
Correct |
2 ms |
2636 KB |
Output is correct |
8 |
Correct |
23 ms |
4460 KB |
Output is correct |
9 |
Correct |
71 ms |
7688 KB |
Output is correct |
10 |
Correct |
72 ms |
7824 KB |
Output is correct |
11 |
Correct |
83 ms |
10004 KB |
Output is correct |
12 |
Correct |
76 ms |
10356 KB |
Output is correct |
13 |
Correct |
70 ms |
7108 KB |
Output is correct |
14 |
Correct |
76 ms |
7516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2672 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
2 ms |
2672 KB |
Output is correct |
7 |
Correct |
2 ms |
2668 KB |
Output is correct |
8 |
Correct |
2 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2672 KB |
Output is correct |
10 |
Correct |
2 ms |
2636 KB |
Output is correct |
11 |
Correct |
3 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 |
3 ms |
2676 KB |
Output is correct |
16 |
Correct |
2 ms |
2668 KB |
Output is correct |
17 |
Correct |
85 ms |
32360 KB |
Output is correct |
18 |
Correct |
90 ms |
31956 KB |
Output is correct |
19 |
Correct |
84 ms |
32560 KB |
Output is correct |
20 |
Correct |
83 ms |
32376 KB |
Output is correct |
21 |
Correct |
81 ms |
31940 KB |
Output is correct |
22 |
Correct |
85 ms |
32472 KB |
Output is correct |
23 |
Correct |
66 ms |
7048 KB |
Output is correct |
24 |
Correct |
77 ms |
7436 KB |
Output is correct |
25 |
Correct |
71 ms |
7492 KB |
Output is correct |
26 |
Correct |
2 ms |
2636 KB |
Output is correct |
27 |
Correct |
23 ms |
4460 KB |
Output is correct |
28 |
Correct |
71 ms |
7688 KB |
Output is correct |
29 |
Correct |
72 ms |
7824 KB |
Output is correct |
30 |
Correct |
83 ms |
10004 KB |
Output is correct |
31 |
Correct |
76 ms |
10356 KB |
Output is correct |
32 |
Correct |
70 ms |
7108 KB |
Output is correct |
33 |
Correct |
76 ms |
7516 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 |
2 ms |
2636 KB |
Output is correct |
40 |
Correct |
2 ms |
2636 KB |
Output is correct |
41 |
Correct |
2 ms |
2636 KB |
Output is correct |
42 |
Correct |
3 ms |
2676 KB |
Output is correct |
43 |
Correct |
2 ms |
2636 KB |
Output is correct |
44 |
Correct |
2 ms |
2636 KB |
Output is correct |
45 |
Correct |
82 ms |
32368 KB |
Output is correct |
46 |
Correct |
83 ms |
32036 KB |
Output is correct |
47 |
Correct |
87 ms |
32452 KB |
Output is correct |
48 |
Correct |
73 ms |
7084 KB |
Output is correct |
49 |
Correct |
82 ms |
7352 KB |
Output is correct |
50 |
Correct |
74 ms |
7484 KB |
Output is correct |
51 |
Correct |
3 ms |
2680 KB |
Output is correct |
52 |
Correct |
23 ms |
4428 KB |
Output is correct |
53 |
Correct |
73 ms |
7628 KB |
Output is correct |
54 |
Correct |
76 ms |
7760 KB |
Output is correct |
55 |
Correct |
79 ms |
9924 KB |
Output is correct |
56 |
Correct |
76 ms |
10368 KB |
Output is correct |
57 |
Correct |
66 ms |
7112 KB |
Output is correct |
58 |
Correct |
72 ms |
7508 KB |
Output is correct |
59 |
Correct |
23 ms |
4340 KB |
Output is correct |
60 |
Correct |
67 ms |
7108 KB |
Output is correct |
61 |
Correct |
74 ms |
7620 KB |
Output is correct |
62 |
Correct |
74 ms |
7748 KB |
Output is correct |
63 |
Correct |
76 ms |
7800 KB |
Output is correct |
64 |
Correct |
72 ms |
7672 KB |
Output is correct |
65 |
Correct |
58 ms |
8008 KB |
Output is correct |
66 |
Correct |
57 ms |
8004 KB |
Output is correct |
67 |
Correct |
55 ms |
11444 KB |
Output is correct |
68 |
Correct |
58 ms |
11420 KB |
Output is correct |
69 |
Correct |
55 ms |
11416 KB |
Output is correct |
70 |
Correct |
54 ms |
11404 KB |
Output is correct |