# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
502962 | sliviu | Connecting Supertrees (IOI20_supertrees) | C++14 | 1 ms | 332 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;
int construct(vector<vector<int>> p) {
int n = p.size(), cur = 0;
vector<vector<int>> ans(n, vector<int>(n));
vector<int> seen(n), solved(n), cycle;
function<void(int)> dfs = [&](int node) {
seen[node] = cur;
int c1 = 0, c2 = 0;
for (int i = 0; i < n; ++i)
if (i != node) {
if (p[node][i] == 1)
++c1;
else if (p[node][i] == 2)
++c2;
else if (p[node][i] == 3)
return 0;
if (!seen[i] && p[node][i])
dfs(i);
if (!p[node][i] && seen[i])
return 0;
}
if (!c1 && c2)
cycle.emplace_back(node);
if (!solved[cur] && c1) {
solved[cur] = 1;
int cur = node;
for (int i = 0; i < n; ++i)
if (i != node && p[node][i] == 1)
ans[cur][i] = ans[i][cur] = 1, cur = i;
}
};
for (int i = 0; i < n; ++i)
if (!seen[i]) {
cycle.clear();
++cur;
dfs(i);
if (!cycle.empty()) {
int cur = i;
for (auto x : cycle)
if (x != i) {
ans[cur][x] = ans[x][cur] = 1;
cur = x;
}
ans[cur][i] = ans[i][cur] = 1;
}
}
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... |