# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
461304 | 2021-08-09T17:19:52 Z | armand | Connecting Supertrees (IOI20_supertrees) | C++14 | 423 ms | 25996 KB |
#include "supertrees.h" #include <vector> int pp[1001][1001]; int n; std::vector<std::vector<int>> answer; bool all1() { int i, j; for (i = 0; i < n; i++) for (j = 0; j < n; j++) if (pp[i][j] != 1) return false; return true; } bool all01() { int i, j; for (i = 0; i < n; i++) for (j = 0; j < n; j++) if (pp[i][j] > 1) return false; return true; } void solve1() { int i; for (i = 0; i < n - 1; i++) { answer[i][i + 1] = 1; answer[i + 1][i] = 1; } } int color[1001]; int nodes[1001]; int nn; bool flag2; void dfs(int u, int prnt) { int j; if (prnt == -1) { std::vector<int> v; for (j = 0; j < n; j++) if (pp[u][j]) v.push_back(j); for (j = 0; j < v.size() - 1; j++) if (!pp[v[j]][v[j + 1]]) flag2 = false; if (v.size() > 1 && !pp[v[0]][v.size() - 1]) flag2 = false; } for(j=0; j<n; j++) if (pp[u][j] && !color[j]) { nodes[nn++] = j; color[j] = 1; if (prnt != -1 && !pp[j][prnt]) flag2 = false; dfs(j, u); } } void solve2() { int i, j; for (i = 0; i < n; i++) { if (!color[i]) { nn = 0; color[i] = 1; dfs(i, -1); for (j = 1; j < nn; j++) { answer[nodes[j]][nodes[j - 1]] = 1; answer[nodes[j - 1]][nodes[j]] = 1; } } } } int construct(std::vector<std::vector<int>> p) { n = p.size(); int i, j, k; for (i = 0; i < n; i++) for (j = i + 1; j < n; j++) if (p[i][j]) for (k = j + 1; k < n; k++) if (p[j][k] && !p[i][k]) return 0; for (i = 0; i < n; i++) for (j = 0; j < n; j++) pp[i][j] = p[i][j]; for (int i = 0; i < n; i++) { std::vector<int> row; row.resize(n); answer.push_back(row); } if (all1()) solve1(); else if (all01()) { flag2 = true; solve2(); if (flag2) { build(answer); return 1; } else return 0; } build(answer); return 1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 332 KB | Output is correct |
6 | Correct | 12 ms | 1948 KB | Output is correct |
7 | Correct | 423 ms | 25980 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 332 KB | Output is correct |
6 | Correct | 12 ms | 1948 KB | Output is correct |
7 | Correct | 423 ms | 25980 KB | Output is correct |
8 | Correct | 0 ms | 204 KB | Output is correct |
9 | Correct | 0 ms | 204 KB | Output is correct |
10 | Correct | 0 ms | 204 KB | Output is correct |
11 | Correct | 0 ms | 332 KB | Output is correct |
12 | Correct | 10 ms | 1868 KB | Output is correct |
13 | Correct | 244 ms | 25996 KB | Output is correct |
14 | Correct | 0 ms | 204 KB | Output is correct |
15 | Correct | 0 ms | 204 KB | Output is correct |
16 | Correct | 5 ms | 588 KB | Output is correct |
17 | Correct | 108 ms | 8056 KB | Output is correct |
18 | Correct | 0 ms | 204 KB | Output is correct |
19 | Correct | 0 ms | 204 KB | Output is correct |
20 | Incorrect | 38 ms | 5120 KB | Answer gives possible 0 while actual possible 1 |
21 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Incorrect | 0 ms | 204 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 | 204 KB | Output is correct |
2 | Incorrect | 0 ms | 204 KB | Too few ways to get from 0 to 1, should be 2 found 0 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 332 KB | Output is correct |
6 | Correct | 12 ms | 1948 KB | Output is correct |
7 | Correct | 423 ms | 25980 KB | Output is correct |
8 | Correct | 0 ms | 204 KB | Output is correct |
9 | Correct | 0 ms | 204 KB | Output is correct |
10 | Correct | 0 ms | 204 KB | Output is correct |
11 | Correct | 0 ms | 332 KB | Output is correct |
12 | Correct | 10 ms | 1868 KB | Output is correct |
13 | Correct | 244 ms | 25996 KB | Output is correct |
14 | Correct | 0 ms | 204 KB | Output is correct |
15 | Correct | 0 ms | 204 KB | Output is correct |
16 | Correct | 5 ms | 588 KB | Output is correct |
17 | Correct | 108 ms | 8056 KB | Output is correct |
18 | Correct | 0 ms | 204 KB | Output is correct |
19 | Correct | 0 ms | 204 KB | Output is correct |
20 | Incorrect | 38 ms | 5120 KB | Answer gives possible 0 while actual possible 1 |
21 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 332 KB | Output is correct |
6 | Correct | 12 ms | 1948 KB | Output is correct |
7 | Correct | 423 ms | 25980 KB | Output is correct |
8 | Correct | 0 ms | 204 KB | Output is correct |
9 | Correct | 0 ms | 204 KB | Output is correct |
10 | Correct | 0 ms | 204 KB | Output is correct |
11 | Correct | 0 ms | 332 KB | Output is correct |
12 | Correct | 10 ms | 1868 KB | Output is correct |
13 | Correct | 244 ms | 25996 KB | Output is correct |
14 | Correct | 0 ms | 204 KB | Output is correct |
15 | Correct | 0 ms | 204 KB | Output is correct |
16 | Correct | 5 ms | 588 KB | Output is correct |
17 | Correct | 108 ms | 8056 KB | Output is correct |
18 | Correct | 0 ms | 204 KB | Output is correct |
19 | Correct | 0 ms | 204 KB | Output is correct |
20 | Incorrect | 38 ms | 5120 KB | Answer gives possible 0 while actual possible 1 |
21 | Halted | 0 ms | 0 KB | - |