# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
409750 | 2021-05-21T12:57:08 Z | shahriarkhan | The Xana coup (BOI21_xanadu) | C++14 | 100 ms | 21568 KB |
#include<bits/stdc++.h> using namespace std ; const int INF = 1e9 , mx = 1e5 + 5 ; vector<int> adj[mx] ; long long dp[mx][2][2] ; int col[mx] ; void calc(int s , int p) { long long add1 = INF , add2 = INF , cnt1 = 0 , cnt2 = 0 , tot1 = 0 , tot2 = 0 ; for(int t : adj[s]) { if(t==p) continue ; calc(t,s) ; if(dp[t][0][1]<dp[t][0][0]) { ++cnt1 ; tot1 += dp[t][0][1] ; add1 = min(add1,dp[t][0][0] - dp[t][0][1]) ; } else { tot1 += dp[t][0][0] ; add1 = min(add1,dp[t][0][1] - dp[t][0][0]) ; } if(dp[t][1][1]<dp[t][1][0]) { ++cnt2 ; tot2 += dp[t][1][1] ; add2 = min(add2,dp[t][1][0] - dp[t][1][1]) ; } else { tot2 += dp[t][1][0] ; add2 = min(add2,dp[t][1][1] - dp[t][1][0]) ; } } dp[s][1][0] = tot1 ; dp[s][1][1] = tot2 + 1 ; dp[s][0][0] = tot1 ; dp[s][0][1] = tot2 + 1 ; if(!col[s]) { if(cnt1&1) dp[s][0][0] += add1 ; else dp[s][1][0] += add1 ; if(cnt2&1) dp[s][1][1] += add2 ; else dp[s][0][1] += add2 ; } else { if(cnt1&1) dp[s][1][0] += add1 ; else dp[s][0][0] += add1 ; if(cnt2&1) dp[s][0][1] += add2 ; else dp[s][1][1] += add2 ; } return ; } int main() { int n ; scanf("%d",&n) ; for(int i = 1 ; i < n ; ++i) { int a , b ; scanf("%d%d",&a,&b) ; adj[a].push_back(b) ; adj[b].push_back(a) ; } for(int i = 1 ; i <= n ; ++i) scanf("%d",&col[i]) ; calc(1,0) ; long long ans = min(dp[1][0][0],dp[1][0][1]) ; if(ans>=INF) puts("impossible") ; else printf("%lld\n",ans) ; return 0 ; }
Compilation message
# | 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 | 3 ms | 2636 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 | 3 ms | 2636 KB | Output is correct |
5 | Correct | 2 ms | 2636 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 | 2 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 | 71 ms | 20028 KB | Output is correct |
2 | Correct | 67 ms | 19868 KB | Output is correct |
3 | Correct | 66 ms | 20136 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 65 ms | 20096 KB | Output is correct |
2 | Correct | 76 ms | 19980 KB | Output is correct |
3 | Correct | 72 ms | 20120 KB | Output is correct |
4 | Correct | 62 ms | 8476 KB | Output is correct |
5 | Correct | 67 ms | 10436 KB | Output is correct |
6 | Correct | 88 ms | 10592 KB | Output is correct |
7 | Correct | 2 ms | 2636 KB | Output is correct |
8 | Correct | 22 ms | 5340 KB | Output is correct |
9 | Correct | 70 ms | 10552 KB | Output is correct |
10 | Correct | 76 ms | 10852 KB | Output is correct |
11 | Correct | 73 ms | 11336 KB | Output is correct |
12 | Correct | 79 ms | 11712 KB | Output is correct |
13 | Correct | 68 ms | 10116 KB | Output is correct |
14 | Correct | 77 ms | 10564 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 | 3 ms | 2636 KB | Output is correct |
5 | Correct | 2 ms | 2636 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 | 2 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 | 71 ms | 20028 KB | Output is correct |
18 | Correct | 67 ms | 19868 KB | Output is correct |
19 | Correct | 66 ms | 20136 KB | Output is correct |
20 | Correct | 65 ms | 20096 KB | Output is correct |
21 | Correct | 76 ms | 19980 KB | Output is correct |
22 | Correct | 72 ms | 20120 KB | Output is correct |
23 | Correct | 62 ms | 8476 KB | Output is correct |
24 | Correct | 67 ms | 10436 KB | Output is correct |
25 | Correct | 88 ms | 10592 KB | Output is correct |
26 | Correct | 2 ms | 2636 KB | Output is correct |
27 | Correct | 22 ms | 5340 KB | Output is correct |
28 | Correct | 70 ms | 10552 KB | Output is correct |
29 | Correct | 76 ms | 10852 KB | Output is correct |
30 | Correct | 73 ms | 11336 KB | Output is correct |
31 | Correct | 79 ms | 11712 KB | Output is correct |
32 | Correct | 68 ms | 10116 KB | Output is correct |
33 | Correct | 77 ms | 10564 KB | Output is correct |
34 | Correct | 2 ms | 2636 KB | Output is correct |
35 | Correct | 2 ms | 2720 KB | Output is correct |
36 | Correct | 2 ms | 2656 KB | Output is correct |
37 | Correct | 2 ms | 2644 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 | 2 ms | 2592 KB | Output is correct |
43 | Correct | 2 ms | 2652 KB | Output is correct |
44 | Correct | 2 ms | 2636 KB | Output is correct |
45 | Correct | 86 ms | 21488 KB | Output is correct |
46 | Correct | 75 ms | 21200 KB | Output is correct |
47 | Correct | 77 ms | 21568 KB | Output is correct |
48 | Correct | 62 ms | 9700 KB | Output is correct |
49 | Correct | 78 ms | 10436 KB | Output is correct |
50 | Correct | 87 ms | 10580 KB | Output is correct |
51 | Correct | 2 ms | 2652 KB | Output is correct |
52 | Correct | 22 ms | 5316 KB | Output is correct |
53 | Correct | 81 ms | 10596 KB | Output is correct |
54 | Correct | 78 ms | 10704 KB | Output is correct |
55 | Correct | 100 ms | 11268 KB | Output is correct |
56 | Correct | 72 ms | 11588 KB | Output is correct |
57 | Correct | 63 ms | 10096 KB | Output is correct |
58 | Correct | 80 ms | 10512 KB | Output is correct |
59 | Correct | 21 ms | 5324 KB | Output is correct |
60 | Correct | 65 ms | 9804 KB | Output is correct |
61 | Correct | 77 ms | 10676 KB | Output is correct |
62 | Correct | 71 ms | 10744 KB | Output is correct |
63 | Correct | 67 ms | 10692 KB | Output is correct |
64 | Correct | 71 ms | 10668 KB | Output is correct |
65 | Correct | 61 ms | 11056 KB | Output is correct |
66 | Correct | 62 ms | 11168 KB | Output is correct |
67 | Correct | 60 ms | 11048 KB | Output is correct |
68 | Correct | 54 ms | 10980 KB | Output is correct |
69 | Correct | 72 ms | 11032 KB | Output is correct |
70 | Correct | 54 ms | 11048 KB | Output is correct |