# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
399267 | 2021-05-05T13:44:22 Z | LucaDantas | The Xana coup (BOI21_xanadu) | C++17 | 100 ms | 23348 KB |
#include <bits/stdc++.h> using namespace std; constexpr int maxn = 1e5+10, inf = 0x3f3f3f3f; vector<int> g[maxn]; int dp[maxn][2][2], new_dp[maxn][2][2], state[maxn]; void min_self(int& a, int b) { a = min(a, b); } void dfs(int u, int p = 0) { dp[u][0][state[u]] = 0; dp[u][0][!state[u]] = inf; dp[u][1][state[u]] = inf; dp[u][1][!state[u]] = 1; for(int v : g[u]) { if(v == p) continue; dfs(v, u); for(int i : {0, 1}) { // vou me ativar ou n for(int j : {0, 1}) { // estou ligado ou desligado - ja contando a minha ativação for(int k : {0, 1}) { // ativo-inativo de v for(int l : {0, 1}) { // ligado-desligado de u if(i ^ l) continue; // n posso juntar pq eu preciso garantir q tá todo mundo desligado min_self(new_dp[u][i][j^k], dp[u][i][j] + dp[v][k][l]); } } } } for(int i : {0, 1}) for(int j : {0, 1}) dp[u][i][j] = new_dp[u][i][j], new_dp[u][i][j] = inf; } } int main() { int n; scanf("%d", &n); for(int i = 1, a, b; i < n; i++) scanf("%d %d", &a, &b), g[a].push_back(b), g[b].push_back(a); for(int i = 1; i <= n; i++) scanf("%d", state + i); for(int u = 0; u < maxn; u++) for(int i : {0, 1}) for(int j : {0, 1}) new_dp[u][i][j] = inf; dfs(1); int ans = min(dp[1][0][0], dp[1][1][0]); if(ans == inf) puts("impossible"); else printf("%d\n", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4172 KB | Output is correct |
2 | Correct | 3 ms | 4172 KB | Output is correct |
3 | Correct | 3 ms | 4172 KB | Output is correct |
4 | Correct | 3 ms | 4172 KB | Output is correct |
5 | Correct | 3 ms | 4172 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4172 KB | Output is correct |
2 | Correct | 3 ms | 4172 KB | Output is correct |
3 | Correct | 3 ms | 4172 KB | Output is correct |
4 | Correct | 3 ms | 4172 KB | Output is correct |
5 | Correct | 3 ms | 4172 KB | Output is correct |
6 | Correct | 3 ms | 4180 KB | Output is correct |
7 | Correct | 3 ms | 4172 KB | Output is correct |
8 | Correct | 3 ms | 4148 KB | Output is correct |
9 | Correct | 3 ms | 4172 KB | Output is correct |
10 | Correct | 3 ms | 4172 KB | Output is correct |
11 | Correct | 3 ms | 4172 KB | Output is correct |
12 | Correct | 3 ms | 4172 KB | Output is correct |
13 | Correct | 3 ms | 4172 KB | Output is correct |
14 | Correct | 3 ms | 4172 KB | Output is correct |
15 | Correct | 3 ms | 4172 KB | Output is correct |
16 | Correct | 3 ms | 4172 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 72 ms | 23172 KB | Output is correct |
2 | Correct | 69 ms | 22948 KB | Output is correct |
3 | Correct | 73 ms | 23304 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 75 ms | 23224 KB | Output is correct |
2 | Correct | 70 ms | 22960 KB | Output is correct |
3 | Correct | 78 ms | 23348 KB | Output is correct |
4 | Correct | 62 ms | 8644 KB | Output is correct |
5 | Correct | 72 ms | 9104 KB | Output is correct |
6 | Correct | 75 ms | 9248 KB | Output is correct |
7 | Correct | 3 ms | 4172 KB | Output is correct |
8 | Correct | 23 ms | 5960 KB | Output is correct |
9 | Correct | 71 ms | 9312 KB | Output is correct |
10 | Correct | 76 ms | 9440 KB | Output is correct |
11 | Correct | 74 ms | 10232 KB | Output is correct |
12 | Correct | 75 ms | 10564 KB | Output is correct |
13 | Correct | 66 ms | 8904 KB | Output is correct |
14 | Correct | 100 ms | 9196 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4172 KB | Output is correct |
2 | Correct | 3 ms | 4172 KB | Output is correct |
3 | Correct | 3 ms | 4172 KB | Output is correct |
4 | Correct | 3 ms | 4172 KB | Output is correct |
5 | Correct | 3 ms | 4172 KB | Output is correct |
6 | Correct | 3 ms | 4180 KB | Output is correct |
7 | Correct | 3 ms | 4172 KB | Output is correct |
8 | Correct | 3 ms | 4148 KB | Output is correct |
9 | Correct | 3 ms | 4172 KB | Output is correct |
10 | Correct | 3 ms | 4172 KB | Output is correct |
11 | Correct | 3 ms | 4172 KB | Output is correct |
12 | Correct | 3 ms | 4172 KB | Output is correct |
13 | Correct | 3 ms | 4172 KB | Output is correct |
14 | Correct | 3 ms | 4172 KB | Output is correct |
15 | Correct | 3 ms | 4172 KB | Output is correct |
16 | Correct | 3 ms | 4172 KB | Output is correct |
17 | Correct | 72 ms | 23172 KB | Output is correct |
18 | Correct | 69 ms | 22948 KB | Output is correct |
19 | Correct | 73 ms | 23304 KB | Output is correct |
20 | Correct | 75 ms | 23224 KB | Output is correct |
21 | Correct | 70 ms | 22960 KB | Output is correct |
22 | Correct | 78 ms | 23348 KB | Output is correct |
23 | Correct | 62 ms | 8644 KB | Output is correct |
24 | Correct | 72 ms | 9104 KB | Output is correct |
25 | Correct | 75 ms | 9248 KB | Output is correct |
26 | Correct | 3 ms | 4172 KB | Output is correct |
27 | Correct | 23 ms | 5960 KB | Output is correct |
28 | Correct | 71 ms | 9312 KB | Output is correct |
29 | Correct | 76 ms | 9440 KB | Output is correct |
30 | Correct | 74 ms | 10232 KB | Output is correct |
31 | Correct | 75 ms | 10564 KB | Output is correct |
32 | Correct | 66 ms | 8904 KB | Output is correct |
33 | Correct | 100 ms | 9196 KB | Output is correct |
34 | Correct | 3 ms | 4172 KB | Output is correct |
35 | Correct | 3 ms | 4172 KB | Output is correct |
36 | Correct | 3 ms | 4172 KB | Output is correct |
37 | Correct | 3 ms | 4172 KB | Output is correct |
38 | Correct | 3 ms | 4172 KB | Output is correct |
39 | Correct | 3 ms | 4172 KB | Output is correct |
40 | Correct | 3 ms | 4172 KB | Output is correct |
41 | Correct | 3 ms | 4172 KB | Output is correct |
42 | Correct | 4 ms | 4172 KB | Output is correct |
43 | Correct | 3 ms | 4172 KB | Output is correct |
44 | Correct | 3 ms | 4172 KB | Output is correct |
45 | Correct | 90 ms | 23264 KB | Output is correct |
46 | Correct | 82 ms | 22980 KB | Output is correct |
47 | Correct | 74 ms | 23304 KB | Output is correct |
48 | Correct | 62 ms | 8736 KB | Output is correct |
49 | Correct | 70 ms | 9092 KB | Output is correct |
50 | Correct | 75 ms | 9272 KB | Output is correct |
51 | Correct | 3 ms | 4224 KB | Output is correct |
52 | Correct | 22 ms | 5956 KB | Output is correct |
53 | Correct | 77 ms | 9296 KB | Output is correct |
54 | Correct | 79 ms | 9436 KB | Output is correct |
55 | Correct | 71 ms | 10308 KB | Output is correct |
56 | Correct | 73 ms | 10536 KB | Output is correct |
57 | Correct | 71 ms | 8984 KB | Output is correct |
58 | Correct | 75 ms | 9160 KB | Output is correct |
59 | Correct | 22 ms | 5936 KB | Output is correct |
60 | Correct | 63 ms | 8796 KB | Output is correct |
61 | Correct | 72 ms | 9244 KB | Output is correct |
62 | Correct | 75 ms | 9412 KB | Output is correct |
63 | Correct | 72 ms | 9332 KB | Output is correct |
64 | Correct | 78 ms | 9408 KB | Output is correct |
65 | Correct | 64 ms | 9716 KB | Output is correct |
66 | Correct | 63 ms | 9744 KB | Output is correct |
67 | Correct | 54 ms | 9660 KB | Output is correct |
68 | Correct | 55 ms | 9572 KB | Output is correct |
69 | Correct | 56 ms | 9660 KB | Output is correct |
70 | Correct | 55 ms | 9676 KB | Output is correct |