# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
861973 | 2023-10-17T09:58:28 Z | Trisanu_Das | The Xana coup (BOI21_xanadu) | C++17 | 1000 ms | 14032 KB |
#include <bits/stdc++.h> using namespace std; vector<vector<int>> graph; vector<bool> on, onCopy; vector<int> v1, v2; void toggle(int k) { on[k] = !on[k]; for (int i = 0; i < graph[k].size(); i++) on[graph[k][i]] = !on[graph[k][i]]; } void dfs(int x, bool y, int from) { if (y) v1.push_back(x); else v2.push_back(x); for (int i = 0; i < graph[x].size(); i++) if (graph[x][i] != from) dfs(graph[x][i], !y, x); } int main() { int n; cin >> n; graph.resize(n); on.resize(n); for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; graph[a - 1].push_back(b - 1); graph[b - 1].push_back(a - 1); } for (int i = 0; i < n; i++) { bool a; cin >> a; on[i] = a; } onCopy = on; dfs(0, false, -1); if (v1.size() > v2.size()) swap(v1, v2); int m = INT_MAX; for (int i = 0; i < 1 << v1.size(); i++) { int cnt = 0; for (int j = 0; j < v1.size(); j++) { if (i & 1 << j) { toggle(v1[j]); cnt++; } } for (int j = 0; j < v2.size(); j++) { if (on[v2[j]]) { toggle(v2[j]); cnt++; } } bool allFalse = true; for (int j = 0; j < v1.size(); j++) { if (on[v1[j]]) { allFalse = false; break; } } if (allFalse) m = min(m, cnt); on = onCopy; } if (m == INT_MAX) cout << "impossible\n"; else cout << m << '\n'; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 1 ms | 444 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 1 ms | 444 KB | Output is correct |
6 | Correct | 0 ms | 600 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 1 ms | 348 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
11 | Correct | 21 ms | 348 KB | Output is correct |
12 | Correct | 47 ms | 436 KB | Output is correct |
13 | Correct | 376 ms | 412 KB | Output is correct |
14 | Correct | 177 ms | 412 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1031 ms | 13872 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1048 ms | 14032 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 1 ms | 444 KB | Output is correct |
6 | Correct | 0 ms | 600 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 1 ms | 348 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
11 | Correct | 21 ms | 348 KB | Output is correct |
12 | Correct | 47 ms | 436 KB | Output is correct |
13 | Correct | 376 ms | 412 KB | Output is correct |
14 | Correct | 177 ms | 412 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Execution timed out | 1031 ms | 13872 KB | Time limit exceeded |
18 | Halted | 0 ms | 0 KB | - |