# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
591180 | 2022-07-07T01:03:09 Z | SirCovidThe19th | Connecting Supertrees (IOI20_supertrees) | C++17 | 229 ms | 22356 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] and ((get(i) == get(j) and p[i][j] == 1) or (get(i) != get(j) and p[i][j] == 2)))) 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 | 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 | 0 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 9 ms | 1108 KB | Output is correct |
7 | Correct | 229 ms | 22000 KB | Output is correct |
# | 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 | 0 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 9 ms | 1108 KB | Output is correct |
7 | Correct | 229 ms | 22000 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 0 ms | 212 KB | Output is correct |
11 | Correct | 0 ms | 212 KB | Output is correct |
12 | Correct | 8 ms | 1108 KB | Output is correct |
13 | Correct | 176 ms | 22024 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 0 ms | 212 KB | Output is correct |
16 | Correct | 3 ms | 724 KB | Output is correct |
17 | Correct | 84 ms | 12164 KB | Output is correct |
18 | Correct | 0 ms | 212 KB | Output is correct |
19 | Correct | 0 ms | 212 KB | Output is correct |
20 | Correct | 40 ms | 5708 KB | Output is correct |
21 | Correct | 164 ms | 22176 KB | Output is correct |
22 | Correct | 170 ms | 21960 KB | Output is correct |
23 | Correct | 206 ms | 22356 KB | Output is correct |
24 | Correct | 189 ms | 22028 KB | Output is correct |
25 | Incorrect | 177 ms | 22020 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 | 300 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Incorrect | 0 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 | 5720 KB | Output is correct |
5 | Correct | 169 ms | 21980 KB | Output is correct |
6 | Correct | 179 ms | 21968 KB | Output is correct |
7 | Correct | 189 ms | 21980 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 46 ms | 5760 KB | Output is correct |
10 | Correct | 162 ms | 21964 KB | Output is correct |
11 | Correct | 160 ms | 22032 KB | Output is correct |
12 | Correct | 179 ms | 22028 KB | Output is correct |
13 | Correct | 1 ms | 212 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 0 ms | 212 KB | Output is correct |
16 | Correct | 42 ms | 5764 KB | Output is correct |
17 | Correct | 195 ms | 21964 KB | Output is correct |
18 | Correct | 161 ms | 22024 KB | Output is correct |
19 | Correct | 188 ms | 22020 KB | Output is correct |
20 | Correct | 179 ms | 22020 KB | Output is correct |
# | 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 | 0 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 9 ms | 1108 KB | Output is correct |
7 | Correct | 229 ms | 22000 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 0 ms | 212 KB | Output is correct |
11 | Correct | 0 ms | 212 KB | Output is correct |
12 | Correct | 8 ms | 1108 KB | Output is correct |
13 | Correct | 176 ms | 22024 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 0 ms | 212 KB | Output is correct |
16 | Correct | 3 ms | 724 KB | Output is correct |
17 | Correct | 84 ms | 12164 KB | Output is correct |
18 | Correct | 0 ms | 212 KB | Output is correct |
19 | Correct | 0 ms | 212 KB | Output is correct |
20 | Correct | 40 ms | 5708 KB | Output is correct |
21 | Correct | 164 ms | 22176 KB | Output is correct |
22 | Correct | 170 ms | 21960 KB | Output is correct |
23 | Correct | 206 ms | 22356 KB | Output is correct |
24 | Correct | 189 ms | 22028 KB | Output is correct |
25 | Incorrect | 177 ms | 22020 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 | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 9 ms | 1108 KB | Output is correct |
7 | Correct | 229 ms | 22000 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 0 ms | 212 KB | Output is correct |
11 | Correct | 0 ms | 212 KB | Output is correct |
12 | Correct | 8 ms | 1108 KB | Output is correct |
13 | Correct | 176 ms | 22024 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 0 ms | 212 KB | Output is correct |
16 | Correct | 3 ms | 724 KB | Output is correct |
17 | Correct | 84 ms | 12164 KB | Output is correct |
18 | Correct | 0 ms | 212 KB | Output is correct |
19 | Correct | 0 ms | 212 KB | Output is correct |
20 | Correct | 40 ms | 5708 KB | Output is correct |
21 | Correct | 164 ms | 22176 KB | Output is correct |
22 | Correct | 170 ms | 21960 KB | Output is correct |
23 | Correct | 206 ms | 22356 KB | Output is correct |
24 | Correct | 189 ms | 22028 KB | Output is correct |
25 | Incorrect | 177 ms | 22020 KB | Answer gives possible 1 while actual possible 0 |
26 | Halted | 0 ms | 0 KB | - |