| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 373232 | 2021-03-03T21:55:37 Z | Matteo_Verz | Connecting Supertrees (IOI20_supertrees) | C++17 | 1000 ms | 22380 KB |
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> answer;
vector <int> viz;
vector <int> countroot;
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
vector <bool> isroot(n, false);
for(int i = 0; i < n; i++)
if(viz[i] == comp) isroot[i] = true; // we consider each node as the "root"
vector <int> roots;
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
| # | 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 | 11 ms | 1236 KB | Output is correct |
| 7 | Correct | 248 ms | 22252 KB | Output is correct |
| # | 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 | 11 ms | 1236 KB | Output is correct |
| 7 | Correct | 248 ms | 22252 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 | 17 ms | 1324 KB | Output is correct |
| 13 | Execution timed out | 1004 ms | 22248 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 | 384 KB | Output is correct |
| 8 | Correct | 23 ms | 1324 KB | Output is correct |
| 9 | Execution timed out | 1068 ms | 22300 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 | 74 ms | 5948 KB | Output is correct |
| 5 | Correct | 256 ms | 22380 KB | Output is correct |
| 6 | Correct | 558 ms | 22172 KB | Output is correct |
| 7 | Correct | 260 ms | 22252 KB | Output is correct |
| 8 | Correct | 1 ms | 364 KB | Output is correct |
| 9 | Correct | 71 ms | 5868 KB | Output is correct |
| 10 | Correct | 258 ms | 22288 KB | Output is correct |
| 11 | Correct | 386 ms | 22172 KB | Output is correct |
| 12 | Correct | 260 ms | 22252 KB | Output is correct |
| 13 | Correct | 1 ms | 364 KB | Output is correct |
| 14 | Correct | 1 ms | 372 KB | Output is correct |
| 15 | Correct | 1 ms | 364 KB | Output is correct |
| 16 | Correct | 76 ms | 5948 KB | Output is correct |
| 17 | Correct | 266 ms | 22316 KB | Output is correct |
| 18 | Correct | 257 ms | 22252 KB | Output is correct |
| 19 | Correct | 303 ms | 22252 KB | Output is correct |
| 20 | Correct | 961 ms | 22220 KB | Output is correct |
| # | 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 | 11 ms | 1236 KB | Output is correct |
| 7 | Correct | 248 ms | 22252 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 | 17 ms | 1324 KB | Output is correct |
| 13 | Execution timed out | 1004 ms | 22248 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 | 11 ms | 1236 KB | Output is correct |
| 7 | Correct | 248 ms | 22252 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 | 17 ms | 1324 KB | Output is correct |
| 13 | Execution timed out | 1004 ms | 22248 KB | Time limit exceeded |
| 14 | Halted | 0 ms | 0 KB | - |