# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
301562 | 2020-09-18T04:29:07 Z | jwvg0425 | Connecting Supertrees (IOI20_supertrees) | C++17 | 272 ms | 22264 KB |
#include "supertrees.h" #include <vector> using namespace std; int cpar[1005]; int tpar[1005]; int tfind(int x) { if (tpar[x] == x) return x; return tpar[x] = tfind(tpar[x]); } void tmerge(int x, int y) { x = tfind(x); y = tfind(y); tpar[x] = y; } int cfind(int x) { if (cpar[x] == x) return x; return cpar[x] = cfind(cpar[x]); } void cmerge(int x, int y) { x = cfind(x); y = cfind(y); cpar[x] = y; } int construct(vector<vector<int>> p) { int n = p.size(); for (int i = 0; i < n; i++) cpar[i] = tpar[i] = i; vector<vector<int>> answer; for (int i = 0; i < n; i++) { vector<int> row; row.resize(n); answer.push_back(row); } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (p[i][j] == 0) continue; if (p[i][j] == 1) { if (tfind(i) == tfind(j)) continue; tmerge(i, j); answer[i][j] = answer[j][i] = 1; continue; } if (p[i][j] == 2) cmerge(i, j); } } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (p[i][j] == 0) { if (cfind(i) == cfind(j) || tfind(i) == tfind(j)) return 0; } if (p[i][j] == 1) { if (cfind(i) == cfind(j) || tfind(i) != tfind(j)) return 0; } if (p[i][j] == 2) { if (cfind(i) != cfind(j) || tfind(i) == tfind(j)) return 0; } } } for (int i = 0; i < n; i++) { if (cfind(i) != i) continue; vector<int> cs; for (int j = 0; j < n; j++) if (cfind(j) == i) cs.push_back(j); if (cs.size() < 2) continue; for (int x = 0; x < cs.size(); x++) { int nx = (x + 1) % cs.size(); answer[cs[x]][cs[nx]] = answer[cs[nx]][cs[x]] = 1; } } build(answer); return 1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 256 KB | Output is correct |
2 | Correct | 0 ms | 256 KB | Output is correct |
3 | Correct | 0 ms | 256 KB | Output is correct |
4 | Correct | 0 ms | 256 KB | Output is correct |
5 | Correct | 0 ms | 256 KB | Output is correct |
6 | Correct | 13 ms | 1280 KB | Output is correct |
7 | Correct | 258 ms | 22136 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 256 KB | Output is correct |
2 | Correct | 0 ms | 256 KB | Output is correct |
3 | Correct | 0 ms | 256 KB | Output is correct |
4 | Correct | 0 ms | 256 KB | Output is correct |
5 | Correct | 0 ms | 256 KB | Output is correct |
6 | Correct | 13 ms | 1280 KB | Output is correct |
7 | Correct | 258 ms | 22136 KB | Output is correct |
8 | Correct | 0 ms | 256 KB | Output is correct |
9 | Correct | 1 ms | 416 KB | Output is correct |
10 | Correct | 0 ms | 256 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 11 ms | 1152 KB | Output is correct |
13 | Correct | 260 ms | 22136 KB | Output is correct |
14 | Correct | 0 ms | 384 KB | Output is correct |
15 | Correct | 1 ms | 384 KB | Output is correct |
16 | Correct | 5 ms | 768 KB | Output is correct |
17 | Correct | 132 ms | 12152 KB | Output is correct |
18 | Correct | 0 ms | 256 KB | Output is correct |
19 | Correct | 0 ms | 256 KB | Output is correct |
20 | Correct | 64 ms | 5752 KB | Output is correct |
21 | Correct | 261 ms | 22136 KB | Output is correct |
22 | Correct | 253 ms | 22136 KB | Output is correct |
23 | Correct | 265 ms | 22136 KB | Output is correct |
24 | Correct | 252 ms | 22140 KB | Output is correct |
25 | Correct | 112 ms | 12152 KB | Output is correct |
26 | Correct | 111 ms | 12152 KB | Output is correct |
27 | Correct | 270 ms | 22136 KB | Output is correct |
28 | Correct | 256 ms | 22136 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 256 KB | Output is correct |
2 | Correct | 0 ms | 256 KB | Output is correct |
3 | Correct | 0 ms | 256 KB | Output is correct |
4 | Incorrect | 0 ms | 256 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 | 256 KB | Output is correct |
2 | Correct | 0 ms | 256 KB | Output is correct |
3 | Correct | 0 ms | 256 KB | Output is correct |
4 | Correct | 64 ms | 5752 KB | Output is correct |
5 | Correct | 266 ms | 22264 KB | Output is correct |
6 | Correct | 251 ms | 22136 KB | Output is correct |
7 | Correct | 266 ms | 22136 KB | Output is correct |
8 | Correct | 0 ms | 256 KB | Output is correct |
9 | Correct | 63 ms | 5752 KB | Output is correct |
10 | Correct | 259 ms | 22136 KB | Output is correct |
11 | Correct | 248 ms | 22136 KB | Output is correct |
12 | Correct | 272 ms | 22136 KB | Output is correct |
13 | Correct | 0 ms | 256 KB | Output is correct |
14 | Correct | 0 ms | 256 KB | Output is correct |
15 | Incorrect | 0 ms | 256 KB | Answer gives possible 0 while actual possible 1 |
16 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 256 KB | Output is correct |
2 | Correct | 0 ms | 256 KB | Output is correct |
3 | Correct | 0 ms | 256 KB | Output is correct |
4 | Correct | 0 ms | 256 KB | Output is correct |
5 | Correct | 0 ms | 256 KB | Output is correct |
6 | Correct | 13 ms | 1280 KB | Output is correct |
7 | Correct | 258 ms | 22136 KB | Output is correct |
8 | Correct | 0 ms | 256 KB | Output is correct |
9 | Correct | 1 ms | 416 KB | Output is correct |
10 | Correct | 0 ms | 256 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 11 ms | 1152 KB | Output is correct |
13 | Correct | 260 ms | 22136 KB | Output is correct |
14 | Correct | 0 ms | 384 KB | Output is correct |
15 | Correct | 1 ms | 384 KB | Output is correct |
16 | Correct | 5 ms | 768 KB | Output is correct |
17 | Correct | 132 ms | 12152 KB | Output is correct |
18 | Correct | 0 ms | 256 KB | Output is correct |
19 | Correct | 0 ms | 256 KB | Output is correct |
20 | Correct | 64 ms | 5752 KB | Output is correct |
21 | Correct | 261 ms | 22136 KB | Output is correct |
22 | Correct | 253 ms | 22136 KB | Output is correct |
23 | Correct | 265 ms | 22136 KB | Output is correct |
24 | Correct | 252 ms | 22140 KB | Output is correct |
25 | Correct | 112 ms | 12152 KB | Output is correct |
26 | Correct | 111 ms | 12152 KB | Output is correct |
27 | Correct | 270 ms | 22136 KB | Output is correct |
28 | Correct | 256 ms | 22136 KB | Output is correct |
29 | Correct | 0 ms | 256 KB | Output is correct |
30 | Correct | 0 ms | 256 KB | Output is correct |
31 | Correct | 0 ms | 256 KB | Output is correct |
32 | Incorrect | 0 ms | 256 KB | Answer gives possible 1 while actual possible 0 |
33 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 256 KB | Output is correct |
2 | Correct | 0 ms | 256 KB | Output is correct |
3 | Correct | 0 ms | 256 KB | Output is correct |
4 | Correct | 0 ms | 256 KB | Output is correct |
5 | Correct | 0 ms | 256 KB | Output is correct |
6 | Correct | 13 ms | 1280 KB | Output is correct |
7 | Correct | 258 ms | 22136 KB | Output is correct |
8 | Correct | 0 ms | 256 KB | Output is correct |
9 | Correct | 1 ms | 416 KB | Output is correct |
10 | Correct | 0 ms | 256 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 11 ms | 1152 KB | Output is correct |
13 | Correct | 260 ms | 22136 KB | Output is correct |
14 | Correct | 0 ms | 384 KB | Output is correct |
15 | Correct | 1 ms | 384 KB | Output is correct |
16 | Correct | 5 ms | 768 KB | Output is correct |
17 | Correct | 132 ms | 12152 KB | Output is correct |
18 | Correct | 0 ms | 256 KB | Output is correct |
19 | Correct | 0 ms | 256 KB | Output is correct |
20 | Correct | 64 ms | 5752 KB | Output is correct |
21 | Correct | 261 ms | 22136 KB | Output is correct |
22 | Correct | 253 ms | 22136 KB | Output is correct |
23 | Correct | 265 ms | 22136 KB | Output is correct |
24 | Correct | 252 ms | 22140 KB | Output is correct |
25 | Correct | 112 ms | 12152 KB | Output is correct |
26 | Correct | 111 ms | 12152 KB | Output is correct |
27 | Correct | 270 ms | 22136 KB | Output is correct |
28 | Correct | 256 ms | 22136 KB | Output is correct |
29 | Correct | 0 ms | 256 KB | Output is correct |
30 | Correct | 0 ms | 256 KB | Output is correct |
31 | Correct | 0 ms | 256 KB | Output is correct |
32 | Incorrect | 0 ms | 256 KB | Answer gives possible 1 while actual possible 0 |
33 | Halted | 0 ms | 0 KB | - |