# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
301520 | kevinsogo | Connecting Supertrees (IOI20_supertrees) | C++17 | 299 ms | 26236 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<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 (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... |