# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
373237 | 2021-03-03T22:03:33 Z | Matteo_Verz | 슈퍼트리 잇기 (IOI20_supertrees) | C++17 | 1000 ms | 22284 KB |
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; vector <vector <int>> answer; vector <int> viz; vector <int> countroot; vector <int> roots; bitset <1001> isroot; bool ok = true; void Solve_Component(int node, vector <vector <int>> p, int comp) { //cout << "New iteration: Node = " << node << '\n'; int n = p.size(); viz[node] = comp; for(int i = 0; i < n; i++) if(p[node][i] > 0) viz[i] = comp; // mark each node as part of the component for(int i = 0; i < n; i++) isroot.set(i, false); for(int i = 0; i < n; i++) if(viz[i] == comp) isroot[i] = true; // we consider each node as the "root" roots.clear(); for(int i = 0; i < n; i++) { // we go through each node if(isroot[i] == true) { roots.push_back(i); countroot[i]++; if(countroot[i] > 1) { // if the node is a root of more than 1 tree ok = false; return; } for(int j = i + 1; j < n; j++) { if(p[i][j] == 1) { // if there is only 1 path from i to j => i is parent of j answer[i][j] = answer[j][i] = 1; isroot[j] = false; } } } } /*for(int i = 0; i < n; i++) cout << isroot[i] << " "; cout << '\n';*/ if(roots.size() == 1) return; // it's fine, we only have a tree if(roots.size() == 2) { // we have a cycle of length 2 => impossible ok = false; return; } for(int i = 0; i < roots.size() - 1; i++) answer[roots[i]][roots[i + 1]] = answer[roots[i + 1]][roots[i]] = 1; // we connect the roots answer[roots[0]][roots.back()] = answer[roots.back()][roots[0]] = 1; } int construct(vector<vector<int>> p) { int n = p.size(); answer.resize(n); for(int i = 0; i < n; i++) answer[i].resize(n); // last subtask, p[i][j] == 3 for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) if(p[i][j] > 2) return 0; } viz.resize(n); countroot.resize(n); int cc(0); for(int i = 0; i < n; i++) if(viz[i] == 0) Solve_Component(i, p, ++cc); // solve for each component if(ok == false) return 0; build(answer); return 1; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | 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 | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 10 ms | 1236 KB | Output is correct |
7 | Correct | 250 ms | 22140 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | 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 | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 10 ms | 1236 KB | Output is correct |
7 | Correct | 250 ms | 22140 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 | 364 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 18 ms | 1196 KB | Output is correct |
13 | Execution timed out | 1047 ms | 16560 KB | Time limit exceeded |
14 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 0 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 | 1 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 17 ms | 1196 KB | Output is correct |
9 | Execution timed out | 1099 ms | 16332 KB | Time limit exceeded |
10 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 512 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 93 ms | 5780 KB | Output is correct |
5 | Correct | 272 ms | 22284 KB | Output is correct |
6 | Execution timed out | 1092 ms | 20844 KB | Time limit exceeded |
7 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | 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 | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 10 ms | 1236 KB | Output is correct |
7 | Correct | 250 ms | 22140 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 | 364 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 18 ms | 1196 KB | Output is correct |
13 | Execution timed out | 1047 ms | 16560 KB | Time limit exceeded |
14 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | 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 | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 10 ms | 1236 KB | Output is correct |
7 | Correct | 250 ms | 22140 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 | 364 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 18 ms | 1196 KB | Output is correct |
13 | Execution timed out | 1047 ms | 16560 KB | Time limit exceeded |
14 | Halted | 0 ms | 0 KB | - |