# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
301520 | 2020-09-18T03:41:23 Z | kevinsogo | 슈퍼트리 잇기 (IOI20_supertrees) | C++17 | 299 ms | 26236 KB |
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; vector<int> get_comp(const vector<vector<int>>& adj, vector<bool>& vis, int s) { assert(!vis[s]); vis[s] = true; vector<int> que(1, s); for (int f = 0; f < que.size(); f++) { int i = que[f]; assert(vis[i]); for (int j : adj[i]) { if (!vis[j]) { vis[j] = true; que.push_back(j); } } } return que; } int construct(vector<vector<int>> p) { int n = p.size(); vector<vector<int>> ans(n, vector<int>(n)); vector<vector<int>> adjtree(n), adjcycl(n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (p[i][j] == 3) return 0; if (p[i][j] == 1) adjtree[i].push_back(j); } } vector<vector<int>> trees; vector<int> roots; vector<bool> vis(n); for (int s = 0; s < n; s++) { if (!vis[s]) { trees.push_back(get_comp(adjtree, vis, s)); roots.push_back(trees.back().back()); } } for (int t1 = 0; t1 < trees.size(); t1++) { for (int t2 = 0; t2 < trees.size(); t2++) { int target = p[roots[t1]][roots[t2]]; if (target == 0 && t1 == t2) return 0; if (target == 1 && t1 != t2) return 0; if (target == 2 && t1 == t2) return 0; for (int i1 : trees[t1]) for (int i2 : trees[t2]) { if (p[i1][i2] != target) return 0; } } } // build trees for (auto& tree : trees) { for (int i = 1; i < tree.size(); i++) { ans[tree[0]][tree[i]] = 1; } } // build cycles for (int i : roots) for (int j : roots) { if (p[i][j] == 2) adjcycl[i].push_back(j); } vis = vector<bool>(n); for (int s : roots) { if (!vis[s]) { vector<int> cycle = get_comp(adjcycl, vis, s); if (cycle.size() > 1) { for (int i = 0, j = cycle.size() - 1; i < cycle.size(); j = i++) { ans[cycle[i]][cycle[j]] = 1; } } if (cycle.size() == 2) return 0; } } // fix grid for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { ans[i][j] |= ans[j][i]; ans[j][i] |= ans[i][j]; } } for (int i = 0; i < n; i++) { ans[i][i] = 0; } build(ans); return 1; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | 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 | Correct | 1 ms | 256 KB | Output is correct |
5 | Correct | 1 ms | 256 KB | Output is correct |
6 | Correct | 12 ms | 1408 KB | Output is correct |
7 | Correct | 271 ms | 26236 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | 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 | Correct | 1 ms | 256 KB | Output is correct |
5 | Correct | 1 ms | 256 KB | Output is correct |
6 | Correct | 12 ms | 1408 KB | Output is correct |
7 | Correct | 271 ms | 26236 KB | Output is correct |
8 | Correct | 1 ms | 416 KB | Output is correct |
9 | Correct | 0 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 | 11 ms | 1280 KB | Output is correct |
13 | Correct | 286 ms | 22264 KB | Output is correct |
14 | Correct | 1 ms | 256 KB | Output is correct |
15 | Correct | 1 ms | 256 KB | Output is correct |
16 | Correct | 6 ms | 896 KB | Output is correct |
17 | Correct | 129 ms | 14712 KB | Output is correct |
18 | Correct | 1 ms | 256 KB | Output is correct |
19 | Correct | 1 ms | 256 KB | Output is correct |
20 | Correct | 69 ms | 5880 KB | Output is correct |
21 | Correct | 270 ms | 22672 KB | Output is correct |
22 | Correct | 262 ms | 22136 KB | Output is correct |
23 | Correct | 268 ms | 24184 KB | Output is correct |
24 | Correct | 272 ms | 22264 KB | Output is correct |
25 | Correct | 132 ms | 12664 KB | Output is correct |
26 | Correct | 113 ms | 12280 KB | Output is correct |
27 | Correct | 273 ms | 25208 KB | Output is correct |
28 | Correct | 268 ms | 22264 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 416 KB | Output is correct |
2 | Correct | 1 ms | 288 KB | Output is correct |
3 | Correct | 1 ms | 256 KB | Output is correct |
4 | Correct | 0 ms | 256 KB | Output is correct |
5 | Correct | 1 ms | 256 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 1 ms | 256 KB | Output is correct |
8 | Correct | 11 ms | 1280 KB | Output is correct |
9 | Correct | 299 ms | 22204 KB | Output is correct |
10 | Correct | 1 ms | 256 KB | Output is correct |
11 | Correct | 1 ms | 256 KB | Output is correct |
12 | Correct | 12 ms | 1536 KB | Output is correct |
13 | Correct | 283 ms | 26232 KB | Output is correct |
14 | Incorrect | 1 ms | 256 KB | Answer gives possible 1 while actual possible 0 |
15 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
2 | Correct | 1 ms | 256 KB | Output is correct |
3 | Correct | 0 ms | 256 KB | Output is correct |
4 | Correct | 66 ms | 5880 KB | Output is correct |
5 | Correct | 267 ms | 22648 KB | Output is correct |
6 | Correct | 263 ms | 22136 KB | Output is correct |
7 | Correct | 275 ms | 24184 KB | Output is correct |
8 | Correct | 1 ms | 256 KB | Output is correct |
9 | Correct | 71 ms | 5880 KB | Output is correct |
10 | Correct | 267 ms | 22776 KB | Output is correct |
11 | Correct | 272 ms | 22264 KB | Output is correct |
12 | Correct | 283 ms | 25336 KB | Output is correct |
13 | Correct | 1 ms | 256 KB | Output is correct |
14 | Correct | 1 ms | 256 KB | Output is correct |
15 | Correct | 1 ms | 256 KB | Output is correct |
16 | Correct | 68 ms | 5880 KB | Output is correct |
17 | Correct | 275 ms | 22776 KB | Output is correct |
18 | Correct | 270 ms | 22520 KB | Output is correct |
19 | Correct | 274 ms | 22392 KB | Output is correct |
20 | Correct | 275 ms | 22264 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | 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 | Correct | 1 ms | 256 KB | Output is correct |
5 | Correct | 1 ms | 256 KB | Output is correct |
6 | Correct | 12 ms | 1408 KB | Output is correct |
7 | Correct | 271 ms | 26236 KB | Output is correct |
8 | Correct | 1 ms | 416 KB | Output is correct |
9 | Correct | 0 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 | 11 ms | 1280 KB | Output is correct |
13 | Correct | 286 ms | 22264 KB | Output is correct |
14 | Correct | 1 ms | 256 KB | Output is correct |
15 | Correct | 1 ms | 256 KB | Output is correct |
16 | Correct | 6 ms | 896 KB | Output is correct |
17 | Correct | 129 ms | 14712 KB | Output is correct |
18 | Correct | 1 ms | 256 KB | Output is correct |
19 | Correct | 1 ms | 256 KB | Output is correct |
20 | Correct | 69 ms | 5880 KB | Output is correct |
21 | Correct | 270 ms | 22672 KB | Output is correct |
22 | Correct | 262 ms | 22136 KB | Output is correct |
23 | Correct | 268 ms | 24184 KB | Output is correct |
24 | Correct | 272 ms | 22264 KB | Output is correct |
25 | Correct | 132 ms | 12664 KB | Output is correct |
26 | Correct | 113 ms | 12280 KB | Output is correct |
27 | Correct | 273 ms | 25208 KB | Output is correct |
28 | Correct | 268 ms | 22264 KB | Output is correct |
29 | Correct | 1 ms | 416 KB | Output is correct |
30 | Correct | 1 ms | 288 KB | Output is correct |
31 | Correct | 1 ms | 256 KB | Output is correct |
32 | Correct | 0 ms | 256 KB | Output is correct |
33 | Correct | 1 ms | 256 KB | Output is correct |
34 | Correct | 1 ms | 384 KB | Output is correct |
35 | Correct | 1 ms | 256 KB | Output is correct |
36 | Correct | 11 ms | 1280 KB | Output is correct |
37 | Correct | 299 ms | 22204 KB | Output is correct |
38 | Correct | 1 ms | 256 KB | Output is correct |
39 | Correct | 1 ms | 256 KB | Output is correct |
40 | Correct | 12 ms | 1536 KB | Output is correct |
41 | Correct | 283 ms | 26232 KB | Output is correct |
42 | Incorrect | 1 ms | 256 KB | Answer gives possible 1 while actual possible 0 |
43 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | 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 | Correct | 1 ms | 256 KB | Output is correct |
5 | Correct | 1 ms | 256 KB | Output is correct |
6 | Correct | 12 ms | 1408 KB | Output is correct |
7 | Correct | 271 ms | 26236 KB | Output is correct |
8 | Correct | 1 ms | 416 KB | Output is correct |
9 | Correct | 0 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 | 11 ms | 1280 KB | Output is correct |
13 | Correct | 286 ms | 22264 KB | Output is correct |
14 | Correct | 1 ms | 256 KB | Output is correct |
15 | Correct | 1 ms | 256 KB | Output is correct |
16 | Correct | 6 ms | 896 KB | Output is correct |
17 | Correct | 129 ms | 14712 KB | Output is correct |
18 | Correct | 1 ms | 256 KB | Output is correct |
19 | Correct | 1 ms | 256 KB | Output is correct |
20 | Correct | 69 ms | 5880 KB | Output is correct |
21 | Correct | 270 ms | 22672 KB | Output is correct |
22 | Correct | 262 ms | 22136 KB | Output is correct |
23 | Correct | 268 ms | 24184 KB | Output is correct |
24 | Correct | 272 ms | 22264 KB | Output is correct |
25 | Correct | 132 ms | 12664 KB | Output is correct |
26 | Correct | 113 ms | 12280 KB | Output is correct |
27 | Correct | 273 ms | 25208 KB | Output is correct |
28 | Correct | 268 ms | 22264 KB | Output is correct |
29 | Correct | 1 ms | 416 KB | Output is correct |
30 | Correct | 1 ms | 288 KB | Output is correct |
31 | Correct | 1 ms | 256 KB | Output is correct |
32 | Correct | 0 ms | 256 KB | Output is correct |
33 | Correct | 1 ms | 256 KB | Output is correct |
34 | Correct | 1 ms | 384 KB | Output is correct |
35 | Correct | 1 ms | 256 KB | Output is correct |
36 | Correct | 11 ms | 1280 KB | Output is correct |
37 | Correct | 299 ms | 22204 KB | Output is correct |
38 | Correct | 1 ms | 256 KB | Output is correct |
39 | Correct | 1 ms | 256 KB | Output is correct |
40 | Correct | 12 ms | 1536 KB | Output is correct |
41 | Correct | 283 ms | 26232 KB | Output is correct |
42 | Incorrect | 1 ms | 256 KB | Answer gives possible 1 while actual possible 0 |
43 | Halted | 0 ms | 0 KB | - |