# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
301786 | 2020-09-18T08:04:25 Z | Pro100Yan | Connecting Supertrees (IOI20_supertrees) | C++14 | 271 ms | 22136 KB |
#include "supertrees.h" #include <vector> #include <iostream> #define ll long long #define pb push_back using namespace std; const int N = 20005; vector<vector<int>> ans; int d[N]; int get_parent(int v){ if(v == d[v]) return v; return d[v] = get_parent(d[v]); } void add(int u, int v){ int f = get_parent(u), s = get_parent(v); if(f != s) d[f] = d[s]; } int construct(std::vector<std::vector<int>> p) { int n = p.size(); int fault = 0; for(int i = 0; i < n; i++) d[i] = i; for (int i = 0; i < n; i++) { std::vector<int> row; row.resize(n); ans.push_back(row); } for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(p[i][j]){ add(i, j); } } } int pi, pj; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ pi = get_parent(i); pj = get_parent(j); if(p[i][j]){ if(pi != pj) return 0; if(pi != i) ans[i][pi] = ans[pi][i] = 1; if(pi != j) ans[j][pi] = ans[pi][j] = 1; } else{ if(pi == pj) return 0; } } } build(ans); return 1; } /* 5 1 0 0 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 1 1 1 0 0 1 1 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
2 | Correct | 1 ms | 256 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 256 KB | Output is correct |
5 | Correct | 1 ms | 256 KB | Output is correct |
6 | Correct | 11 ms | 1280 KB | Output is correct |
7 | Correct | 266 ms | 22136 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
2 | Correct | 1 ms | 256 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 256 KB | Output is correct |
5 | Correct | 1 ms | 256 KB | Output is correct |
6 | Correct | 11 ms | 1280 KB | Output is correct |
7 | Correct | 266 ms | 22136 KB | Output is correct |
8 | Correct | 1 ms | 256 KB | Output is correct |
9 | Correct | 1 ms | 256 KB | Output is correct |
10 | Correct | 1 ms | 256 KB | Output is correct |
11 | Correct | 1 ms | 256 KB | Output is correct |
12 | Correct | 10 ms | 1152 KB | Output is correct |
13 | Correct | 241 ms | 22136 KB | Output is correct |
14 | Correct | 1 ms | 384 KB | Output is correct |
15 | Correct | 1 ms | 256 KB | Output is correct |
16 | Correct | 5 ms | 768 KB | Output is correct |
17 | Correct | 120 ms | 12152 KB | Output is correct |
18 | Correct | 1 ms | 256 KB | Output is correct |
19 | Correct | 1 ms | 256 KB | Output is correct |
20 | Correct | 61 ms | 5752 KB | Output is correct |
21 | Correct | 253 ms | 22136 KB | Output is correct |
22 | Correct | 243 ms | 22136 KB | Output is correct |
23 | Correct | 269 ms | 22136 KB | Output is correct |
24 | Correct | 248 ms | 22136 KB | Output is correct |
25 | Correct | 105 ms | 12152 KB | Output is correct |
26 | Correct | 103 ms | 12152 KB | Output is correct |
27 | Correct | 271 ms | 22136 KB | Output is correct |
28 | Correct | 241 ms | 22136 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
2 | Correct | 1 ms | 256 KB | Output is correct |
3 | Correct | 1 ms | 256 KB | Output is correct |
4 | Incorrect | 1 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 | 1 ms | 256 KB | Output is correct |
2 | Incorrect | 1 ms | 256 KB | Too few ways to get from 0 to 1, should be 2 found 1 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
2 | Correct | 1 ms | 256 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 256 KB | Output is correct |
5 | Correct | 1 ms | 256 KB | Output is correct |
6 | Correct | 11 ms | 1280 KB | Output is correct |
7 | Correct | 266 ms | 22136 KB | Output is correct |
8 | Correct | 1 ms | 256 KB | Output is correct |
9 | Correct | 1 ms | 256 KB | Output is correct |
10 | Correct | 1 ms | 256 KB | Output is correct |
11 | Correct | 1 ms | 256 KB | Output is correct |
12 | Correct | 10 ms | 1152 KB | Output is correct |
13 | Correct | 241 ms | 22136 KB | Output is correct |
14 | Correct | 1 ms | 384 KB | Output is correct |
15 | Correct | 1 ms | 256 KB | Output is correct |
16 | Correct | 5 ms | 768 KB | Output is correct |
17 | Correct | 120 ms | 12152 KB | Output is correct |
18 | Correct | 1 ms | 256 KB | Output is correct |
19 | Correct | 1 ms | 256 KB | Output is correct |
20 | Correct | 61 ms | 5752 KB | Output is correct |
21 | Correct | 253 ms | 22136 KB | Output is correct |
22 | Correct | 243 ms | 22136 KB | Output is correct |
23 | Correct | 269 ms | 22136 KB | Output is correct |
24 | Correct | 248 ms | 22136 KB | Output is correct |
25 | Correct | 105 ms | 12152 KB | Output is correct |
26 | Correct | 103 ms | 12152 KB | Output is correct |
27 | Correct | 271 ms | 22136 KB | Output is correct |
28 | Correct | 241 ms | 22136 KB | Output is correct |
29 | Correct | 1 ms | 256 KB | Output is correct |
30 | Correct | 1 ms | 256 KB | Output is correct |
31 | Correct | 1 ms | 256 KB | Output is correct |
32 | Incorrect | 1 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 | 1 ms | 256 KB | Output is correct |
2 | Correct | 1 ms | 256 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 256 KB | Output is correct |
5 | Correct | 1 ms | 256 KB | Output is correct |
6 | Correct | 11 ms | 1280 KB | Output is correct |
7 | Correct | 266 ms | 22136 KB | Output is correct |
8 | Correct | 1 ms | 256 KB | Output is correct |
9 | Correct | 1 ms | 256 KB | Output is correct |
10 | Correct | 1 ms | 256 KB | Output is correct |
11 | Correct | 1 ms | 256 KB | Output is correct |
12 | Correct | 10 ms | 1152 KB | Output is correct |
13 | Correct | 241 ms | 22136 KB | Output is correct |
14 | Correct | 1 ms | 384 KB | Output is correct |
15 | Correct | 1 ms | 256 KB | Output is correct |
16 | Correct | 5 ms | 768 KB | Output is correct |
17 | Correct | 120 ms | 12152 KB | Output is correct |
18 | Correct | 1 ms | 256 KB | Output is correct |
19 | Correct | 1 ms | 256 KB | Output is correct |
20 | Correct | 61 ms | 5752 KB | Output is correct |
21 | Correct | 253 ms | 22136 KB | Output is correct |
22 | Correct | 243 ms | 22136 KB | Output is correct |
23 | Correct | 269 ms | 22136 KB | Output is correct |
24 | Correct | 248 ms | 22136 KB | Output is correct |
25 | Correct | 105 ms | 12152 KB | Output is correct |
26 | Correct | 103 ms | 12152 KB | Output is correct |
27 | Correct | 271 ms | 22136 KB | Output is correct |
28 | Correct | 241 ms | 22136 KB | Output is correct |
29 | Correct | 1 ms | 256 KB | Output is correct |
30 | Correct | 1 ms | 256 KB | Output is correct |
31 | Correct | 1 ms | 256 KB | Output is correct |
32 | Incorrect | 1 ms | 256 KB | Answer gives possible 1 while actual possible 0 |
33 | Halted | 0 ms | 0 KB | - |