# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
362705 | 2021-02-04T07:20:09 Z | abra_stone | Connecting Supertrees (IOI20_supertrees) | C++14 | 305 ms | 28268 KB |
#include "supertrees.h" #include <vector> #define N 1005 using namespace std; int n, gc, gr[N], pa[N], a[N][N]; vector<int> rt; vector<vector<int> > answer; int uni(int p) { if (pa[p] == p) return p; else return pa[p] = uni(pa[p]); } void make_tree(int p) { int i; gr[p] = gc; for (i = 0; i < n; i++) { if (a[p][i] != 1 || gr[i]) continue; answer[p][i] = answer[i][p] = 1; pa[uni(i)] = uni(p); make_tree(i); } } int construct(std::vector<std::vector<int> > P) { n = P.size(); int i, j; vector<int> t; t.clear(); for (i = 0; i < n; i++) t.push_back(0); for (i = 0; i < n; i++) answer.push_back(t); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { a[i][j] = P[i][j]; if (a[i][j] == 3) return 0; } } for (i = 0; i < n; i++) pa[i] = i; for (i = 0; i < n; i++) { if (!gr[i]) { gc++; rt.push_back(i); make_tree(i); } } for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { if (gr[i] == gr[j] && a[i][j] != 1) return 0; if (gr[i] != gr[j] && a[i][j] == 1) return 0; } } for (i = 0; i < rt.size(); i++) { for (j = i + 1; j < rt.size(); j++) { if (a[rt[i]][rt[j]] == 2) { pa[uni(rt[i])] = uni(rt[j]); answer[rt[i]][rt[j]] = answer[rt[j]][rt[i]] = 1; } } } for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { if (uni(i) == uni(j) && a[i][j] == 0) return 0; if (uni(i) != uni(j) && a[i][j] != 0) return 0; } } build(answer); return 1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 512 KB | Output is correct |
2 | Correct | 0 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 11 ms | 2028 KB | Output is correct |
7 | Correct | 292 ms | 26080 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 512 KB | Output is correct |
2 | Correct | 0 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 11 ms | 2028 KB | Output is correct |
7 | Correct | 292 ms | 26080 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 11 ms | 1984 KB | Output is correct |
13 | Correct | 269 ms | 26092 KB | Output is correct |
14 | Correct | 1 ms | 364 KB | Output is correct |
15 | Correct | 1 ms | 364 KB | Output is correct |
16 | Correct | 8 ms | 1644 KB | Output is correct |
17 | Correct | 123 ms | 18156 KB | Output is correct |
18 | Correct | 1 ms | 364 KB | Output is correct |
19 | Correct | 1 ms | 364 KB | Output is correct |
20 | Correct | 98 ms | 8300 KB | Output is correct |
21 | Correct | 305 ms | 28012 KB | Output is correct |
22 | Correct | 264 ms | 28012 KB | Output is correct |
23 | Correct | 274 ms | 28140 KB | Output is correct |
24 | Correct | 257 ms | 28268 KB | Output is correct |
25 | Correct | 119 ms | 18028 KB | Output is correct |
26 | Correct | 122 ms | 18156 KB | Output is correct |
27 | Correct | 279 ms | 28012 KB | Output is correct |
28 | Correct | 259 ms | 28012 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 0 ms | 364 KB | Output is correct |
3 | Correct | 0 ms | 364 KB | Output is correct |
4 | Incorrect | 1 ms | 364 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 | 364 KB | Output is correct |
2 | Correct | 0 ms | 364 KB | Output is correct |
3 | Correct | 0 ms | 364 KB | Output is correct |
4 | Correct | 65 ms | 7788 KB | Output is correct |
5 | Correct | 279 ms | 28012 KB | Output is correct |
6 | Correct | 263 ms | 28012 KB | Output is correct |
7 | Correct | 286 ms | 27984 KB | Output is correct |
8 | Incorrect | 0 ms | 364 KB | Too many ways to get from 0 to 2, should be 2 found no less than 3 |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 512 KB | Output is correct |
2 | Correct | 0 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 11 ms | 2028 KB | Output is correct |
7 | Correct | 292 ms | 26080 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 11 ms | 1984 KB | Output is correct |
13 | Correct | 269 ms | 26092 KB | Output is correct |
14 | Correct | 1 ms | 364 KB | Output is correct |
15 | Correct | 1 ms | 364 KB | Output is correct |
16 | Correct | 8 ms | 1644 KB | Output is correct |
17 | Correct | 123 ms | 18156 KB | Output is correct |
18 | Correct | 1 ms | 364 KB | Output is correct |
19 | Correct | 1 ms | 364 KB | Output is correct |
20 | Correct | 98 ms | 8300 KB | Output is correct |
21 | Correct | 305 ms | 28012 KB | Output is correct |
22 | Correct | 264 ms | 28012 KB | Output is correct |
23 | Correct | 274 ms | 28140 KB | Output is correct |
24 | Correct | 257 ms | 28268 KB | Output is correct |
25 | Correct | 119 ms | 18028 KB | Output is correct |
26 | Correct | 122 ms | 18156 KB | Output is correct |
27 | Correct | 279 ms | 28012 KB | Output is correct |
28 | Correct | 259 ms | 28012 KB | Output is correct |
29 | Correct | 1 ms | 364 KB | Output is correct |
30 | Correct | 0 ms | 364 KB | Output is correct |
31 | Correct | 0 ms | 364 KB | Output is correct |
32 | Incorrect | 1 ms | 364 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 | 512 KB | Output is correct |
2 | Correct | 0 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 11 ms | 2028 KB | Output is correct |
7 | Correct | 292 ms | 26080 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 11 ms | 1984 KB | Output is correct |
13 | Correct | 269 ms | 26092 KB | Output is correct |
14 | Correct | 1 ms | 364 KB | Output is correct |
15 | Correct | 1 ms | 364 KB | Output is correct |
16 | Correct | 8 ms | 1644 KB | Output is correct |
17 | Correct | 123 ms | 18156 KB | Output is correct |
18 | Correct | 1 ms | 364 KB | Output is correct |
19 | Correct | 1 ms | 364 KB | Output is correct |
20 | Correct | 98 ms | 8300 KB | Output is correct |
21 | Correct | 305 ms | 28012 KB | Output is correct |
22 | Correct | 264 ms | 28012 KB | Output is correct |
23 | Correct | 274 ms | 28140 KB | Output is correct |
24 | Correct | 257 ms | 28268 KB | Output is correct |
25 | Correct | 119 ms | 18028 KB | Output is correct |
26 | Correct | 122 ms | 18156 KB | Output is correct |
27 | Correct | 279 ms | 28012 KB | Output is correct |
28 | Correct | 259 ms | 28012 KB | Output is correct |
29 | Correct | 1 ms | 364 KB | Output is correct |
30 | Correct | 0 ms | 364 KB | Output is correct |
31 | Correct | 0 ms | 364 KB | Output is correct |
32 | Incorrect | 1 ms | 364 KB | Answer gives possible 1 while actual possible 0 |
33 | Halted | 0 ms | 0 KB | - |