# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
591179 | 2022-07-07T00:55:51 Z | SirCovidThe19th | Connecting Supertrees (IOI20_supertrees) | C++17 | 192 ms | 24068 KB |
#include <bits/stdc++.h> #include "supertrees.h" using namespace std; #define FOR(i, x, y) for (int i = x; i < y; i++) int construct(vector<vector<int>> p){ int n = p.size(); FOR(i, 0, n) FOR(j, 0, n) if (p[i][j] == 3) return 0; vector<vector<int>> ans(n, vector<int>(n, 0)); bool vis[n] = {}; int par[n]; iota(par, par + n, 0); function<int(int)> get = [&](int i){ return i == par[i] ? i : par[i] = get(par[i]); }; auto merge = [&](int a, int b){ par[get(a)] = get(b); }; FOR(src, 0, n) if (!vis[src]){ vector<int> cmp; FOR(i, 0, n) if (p[src][i]){ cmp.push_back(i); if (vis[i]) return 0; vis[i] = 1; } for (int i : cmp) for (int j : cmp) if (p[i][j] == 1) merge(i, j); for (int i : cmp) for (int j : cmp) if ((p[i][j] == 2 and get(i) == get(j)) or !p[i][j]) return 0; bool use[n] = {}; vector<int> head; for (int i : cmp){ int c = get(i); if (!use[c]) head.push_back(c), use[c] = 1; if (i != c) ans[i][c] = ans[c][i] = 1; } FOR(i, 0, head.size()){ int a = head[i]; int b = head[(i + 1) % head.size()]; if (a != b) ans[a][b] = ans[b][a] = 1; } } build(ans); return 1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 9 ms | 1236 KB | Output is correct |
7 | Correct | 192 ms | 24060 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 9 ms | 1236 KB | Output is correct |
7 | Correct | 192 ms | 24060 KB | Output is correct |
8 | Correct | 0 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 | 0 ms | 212 KB | Output is correct |
12 | Correct | 7 ms | 1256 KB | Output is correct |
13 | Correct | 162 ms | 23948 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 0 ms | 212 KB | Output is correct |
16 | Correct | 4 ms | 796 KB | Output is correct |
17 | Correct | 105 ms | 14068 KB | Output is correct |
18 | Correct | 0 ms | 212 KB | Output is correct |
19 | Correct | 0 ms | 212 KB | Output is correct |
20 | Correct | 42 ms | 6204 KB | Output is correct |
21 | Correct | 174 ms | 23936 KB | Output is correct |
22 | Correct | 158 ms | 23904 KB | Output is correct |
23 | Correct | 183 ms | 24012 KB | Output is correct |
24 | Correct | 176 ms | 23912 KB | Output is correct |
25 | Incorrect | 172 ms | 23984 KB | Answer gives possible 1 while actual possible 0 |
26 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Incorrect | 1 ms | 212 KB | Answer gives possible 1 while actual possible 0 |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 41 ms | 6196 KB | Output is correct |
5 | Correct | 171 ms | 23972 KB | Output is correct |
6 | Correct | 161 ms | 23936 KB | Output is correct |
7 | Correct | 179 ms | 23956 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 41 ms | 6256 KB | Output is correct |
10 | Correct | 163 ms | 23932 KB | Output is correct |
11 | Correct | 172 ms | 24068 KB | Output is correct |
12 | Correct | 169 ms | 23932 KB | Output is correct |
13 | Correct | 1 ms | 212 KB | Output is correct |
14 | Correct | 0 ms | 296 KB | Output is correct |
15 | Correct | 0 ms | 212 KB | Output is correct |
16 | Correct | 45 ms | 6264 KB | Output is correct |
17 | Correct | 161 ms | 23932 KB | Output is correct |
18 | Correct | 163 ms | 23884 KB | Output is correct |
19 | Correct | 160 ms | 23924 KB | Output is correct |
20 | Correct | 178 ms | 24012 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 9 ms | 1236 KB | Output is correct |
7 | Correct | 192 ms | 24060 KB | Output is correct |
8 | Correct | 0 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 | 0 ms | 212 KB | Output is correct |
12 | Correct | 7 ms | 1256 KB | Output is correct |
13 | Correct | 162 ms | 23948 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 0 ms | 212 KB | Output is correct |
16 | Correct | 4 ms | 796 KB | Output is correct |
17 | Correct | 105 ms | 14068 KB | Output is correct |
18 | Correct | 0 ms | 212 KB | Output is correct |
19 | Correct | 0 ms | 212 KB | Output is correct |
20 | Correct | 42 ms | 6204 KB | Output is correct |
21 | Correct | 174 ms | 23936 KB | Output is correct |
22 | Correct | 158 ms | 23904 KB | Output is correct |
23 | Correct | 183 ms | 24012 KB | Output is correct |
24 | Correct | 176 ms | 23912 KB | Output is correct |
25 | Incorrect | 172 ms | 23984 KB | Answer gives possible 1 while actual possible 0 |
26 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 9 ms | 1236 KB | Output is correct |
7 | Correct | 192 ms | 24060 KB | Output is correct |
8 | Correct | 0 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 | 0 ms | 212 KB | Output is correct |
12 | Correct | 7 ms | 1256 KB | Output is correct |
13 | Correct | 162 ms | 23948 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 0 ms | 212 KB | Output is correct |
16 | Correct | 4 ms | 796 KB | Output is correct |
17 | Correct | 105 ms | 14068 KB | Output is correct |
18 | Correct | 0 ms | 212 KB | Output is correct |
19 | Correct | 0 ms | 212 KB | Output is correct |
20 | Correct | 42 ms | 6204 KB | Output is correct |
21 | Correct | 174 ms | 23936 KB | Output is correct |
22 | Correct | 158 ms | 23904 KB | Output is correct |
23 | Correct | 183 ms | 24012 KB | Output is correct |
24 | Correct | 176 ms | 23912 KB | Output is correct |
25 | Incorrect | 172 ms | 23984 KB | Answer gives possible 1 while actual possible 0 |
26 | Halted | 0 ms | 0 KB | - |