# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
568467 | Jomnoi | Connecting Supertrees (IOI20_supertrees) | C++17 | 847 ms | 26424 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 <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
const int MAX_N = 1e3 + 5;
int n;
vector <int> graph[MAX_N];
bool visited[MAX_N];
vector <vector <int>> answer;
int cmp[MAX_N];
int parent[MAX_N];
vector <int> vertex[MAX_N];
int root(int u) {
if(u == parent[u]) {
return u;
}
return parent[u] = root(parent[u]);
}
void dfs(int u) {
visited[u] = true;
for(auto v : graph[u]) {
if(visited[v] == false) {
cmp[v] = cmp[u];
answer[u][v] = answer[v][u] = 1;
dfs(v);
}
}
}
int solve(vector <int> nodes, vector <vector <int>> p) {
bool two = false, three = false;
for(auto u : nodes) {
for(auto v : nodes) {
if(u < v and p[u][v] == 1) {
graph[u].push_back(v);
graph[v].push_back(u);
}
}
}
for(auto u : nodes) {
if(visited[u] == false) {
visited[u] = true;
cmp[u] = u;
dfs(u);
}
}
for(auto u : nodes) {
parent[u] = u;
}
for(auto u : nodes) {
for(auto v : nodes) {
if(u < v and p[u][v] == 2 or p[u][v] == 3) {
if(p[u][v] == 2) {
two = true;
}
else if(p[u][v] == 3) {
three = true;
}
parent[root(cmp[v])] = root(cmp[u]);
}
}
}
if(two == true and three == true) {
return 0;
}
if(two == true or three == true) {
vector <int> cycle;
for(auto u : nodes) {
if(cmp[u] == u) {
cycle.push_back(u);
}
}
if(two == true and cycle.size() <= 2) {
return 0;
}
if(three == true and cycle.size() <= 3) {
return 0;
}
int pr = cycle.back();
for(auto v : cycle) {
answer[v][pr] = answer[pr][v] = 1;
pr = v;
}
if(three == true) {
answer[cycle[0]][cycle[2]] = answer[cycle[2]][cycle[0]] = 1;
}
}
return 1;
}
int construct(vector <vector <int>> p) {
n = p.size();
fill(cmp, cmp + n, -1);
answer.resize(n, vector <int> (n, 0));
iota(parent, parent + n, 0);
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(p[i][j] != 0) {
parent[root(j)] = root(i);
}
}
}
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(p[i][j] == 0 and root(i) == root(j)) {
return 0;
}
}
}
vector <int> components;
for(int i = 0; i < n; i++) {
vertex[root(i)].push_back(i);
if(i == root(i)) {
components.push_back(i);
}
}
for(auto c : components) {
if(solve(vertex[c], p) == 0) {
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... |