# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
647912 | 2022-10-04T14:00:50 Z | thorie | The Xana coup (BOI21_xanadu) | C++17 | 1000 ms | 12640 KB |
#include "bits/stdc++.h" using namespace std; vector<vector<int>> graph; vector<bool> on; vector<bool> onCopy; vector<int> v1; vector<int> 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" << endl; } else { cout << m << endl; } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 0 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 1 ms | 212 KB | Output is correct |
11 | Correct | 31 ms | 212 KB | Output is correct |
12 | Correct | 71 ms | 296 KB | Output is correct |
13 | Correct | 577 ms | 284 KB | Output is correct |
14 | Correct | 294 ms | 300 KB | Output is correct |
15 | Correct | 1 ms | 300 KB | Output is correct |
16 | Correct | 1 ms | 212 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1092 ms | 12640 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1099 ms | 12476 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 0 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 1 ms | 212 KB | Output is correct |
11 | Correct | 31 ms | 212 KB | Output is correct |
12 | Correct | 71 ms | 296 KB | Output is correct |
13 | Correct | 577 ms | 284 KB | Output is correct |
14 | Correct | 294 ms | 300 KB | Output is correct |
15 | Correct | 1 ms | 300 KB | Output is correct |
16 | Correct | 1 ms | 212 KB | Output is correct |
17 | Execution timed out | 1092 ms | 12640 KB | Time limit exceeded |
18 | Halted | 0 ms | 0 KB | - |