# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
373239 | 2021-03-03T22:09:58 Z | Matteo_Verz | Connecting Supertrees (IOI20_supertrees) | C++17 | 1000 ms | 22252 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) { int n = p.size(); vector <int> realnodes; for(int i = 0; i < n; i++) if(p[node][i] > 0 || i == node) { viz[i] = comp; // mark each node as part of the component realnodes.push_back(i); // we keep a vector with only the nodes in the component } for(int i : realnodes) isroot.set(i, false); for(int i : realnodes) if(viz[i] == comp) isroot[i] = true; // we consider each node as the "root" n = realnodes.size(); roots.clear(); for(int i = 0; i < realnodes.size(); i++) { // we go through each node if(isroot[realnodes[i]] == true) { roots.push_back(realnodes[i]); countroot[realnodes[i]]++; if(countroot[realnodes[i]] > 1) { // if the node is a root of more than 1 tree ok = false; return; } for(int j = i + 1; j < realnodes.size(); j++) { if(p[realnodes[i]][realnodes[j]] == 1) { // if there is only 1 path from i to j => i is parent of j answer[realnodes[i]][realnodes[j]] = answer[realnodes[j]][realnodes[i]] = 1; isroot[realnodes[j]] = false; } } } } 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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 512 KB | Output is correct |
2 | Correct | 1 ms | 512 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 12 ms | 1260 KB | Output is correct |
7 | Correct | 240 ms | 22252 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 512 KB | Output is correct |
2 | Correct | 1 ms | 512 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 12 ms | 1260 KB | Output is correct |
7 | Correct | 240 ms | 22252 KB | Output is correct |
8 | Correct | 0 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 | 1260 KB | Output is correct |
13 | Execution timed out | 1084 ms | 16488 KB | Time limit exceeded |
14 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 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 | 14 ms | 1260 KB | Output is correct |
9 | Execution timed out | 1083 ms | 16464 KB | Time limit exceeded |
10 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 68 ms | 5848 KB | Output is correct |
5 | Correct | 248 ms | 22124 KB | Output is correct |
6 | Execution timed out | 1097 ms | 21560 KB | Time limit exceeded |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 512 KB | Output is correct |
2 | Correct | 1 ms | 512 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 12 ms | 1260 KB | Output is correct |
7 | Correct | 240 ms | 22252 KB | Output is correct |
8 | Correct | 0 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 | 1260 KB | Output is correct |
13 | Execution timed out | 1084 ms | 16488 KB | Time limit exceeded |
14 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 512 KB | Output is correct |
2 | Correct | 1 ms | 512 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 12 ms | 1260 KB | Output is correct |
7 | Correct | 240 ms | 22252 KB | Output is correct |
8 | Correct | 0 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 | 1260 KB | Output is correct |
13 | Execution timed out | 1084 ms | 16488 KB | Time limit exceeded |
14 | Halted | 0 ms | 0 KB | - |