# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
461280 | 2021-08-09T16:33:23 Z | armand | 슈퍼트리 잇기 (IOI20_supertrees) | C++14 | 231 ms | 26012 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; 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 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 | 1 ms | 332 KB | Output is correct |
6 | Correct | 10 ms | 1916 KB | Output is correct |
7 | Correct | 223 ms | 25992 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 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 | 1 ms | 332 KB | Output is correct |
6 | Correct | 10 ms | 1916 KB | Output is correct |
7 | Correct | 223 ms | 25992 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 | 1924 KB | Output is correct |
13 | Correct | 231 ms | 26012 KB | Output is correct |
14 | Correct | 0 ms | 204 KB | Output is correct |
15 | Correct | 1 ms | 332 KB | Output is correct |
16 | Correct | 5 ms | 1484 KB | Output is correct |
17 | Correct | 109 ms | 16144 KB | Output is correct |
18 | Correct | 1 ms | 204 KB | Output is correct |
19 | Correct | 1 ms | 204 KB | Output is correct |
20 | Incorrect | 28 ms | 5128 KB | Answer gives possible 0 while actual possible 1 |
21 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | 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 | - |
# | 결과 | 실행 시간 | 메모리 | 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 | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 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 | 1 ms | 332 KB | Output is correct |
6 | Correct | 10 ms | 1916 KB | Output is correct |
7 | Correct | 223 ms | 25992 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 | 1924 KB | Output is correct |
13 | Correct | 231 ms | 26012 KB | Output is correct |
14 | Correct | 0 ms | 204 KB | Output is correct |
15 | Correct | 1 ms | 332 KB | Output is correct |
16 | Correct | 5 ms | 1484 KB | Output is correct |
17 | Correct | 109 ms | 16144 KB | Output is correct |
18 | Correct | 1 ms | 204 KB | Output is correct |
19 | Correct | 1 ms | 204 KB | Output is correct |
20 | Incorrect | 28 ms | 5128 KB | Answer gives possible 0 while actual possible 1 |
21 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 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 | 1 ms | 332 KB | Output is correct |
6 | Correct | 10 ms | 1916 KB | Output is correct |
7 | Correct | 223 ms | 25992 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 | 1924 KB | Output is correct |
13 | Correct | 231 ms | 26012 KB | Output is correct |
14 | Correct | 0 ms | 204 KB | Output is correct |
15 | Correct | 1 ms | 332 KB | Output is correct |
16 | Correct | 5 ms | 1484 KB | Output is correct |
17 | Correct | 109 ms | 16144 KB | Output is correct |
18 | Correct | 1 ms | 204 KB | Output is correct |
19 | Correct | 1 ms | 204 KB | Output is correct |
20 | Incorrect | 28 ms | 5128 KB | Answer gives possible 0 while actual possible 1 |
21 | Halted | 0 ms | 0 KB | - |