# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
373237 | Matteo_Verz | Connecting Supertrees (IOI20_supertrees) | C++17 | 1099 ms | 22284 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |