# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
301445 | qpwoeirut | Connecting Supertrees (IOI20_supertrees) | C++17 | 1 ms | 256 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;
typedef vector<vector<int>> vvi;
const int MN = 1001;
int N;
int root[MN];
int par(int u) {
if (u == root[u]) return u;
root[u] = par(root[u]);
return root[u];
}
void join(int u, int v) {
int ru = par(u), rv = par(v);
if (ru == rv) return;
root[ru] = rv;
}
bool dsu(const vvi& p) {
for (int i=0; i<N; ++i) {
root[i] = i;
}
for (int i=0; i<N; ++i) {
for (int j=0; j<N; ++j) {
if (p[i][j]) join(i, j);
}
}
for (int i=0; i<N; ++i) {
for (int j=0; j<N; ++j) {
if (par(i) == par(j) && p[i][j] == 0) {
return 0;
}
}
}
return 1;
}
int sub2(const vvi& p) {
if (!dsu(p)) return 0;
vvi ans(N, vector<int>(N));
for (int i=0; i<N; ++i) {
if (i != par(i)) {
ans[i][par(i)] = true;
ans[par(i)][i] = true;
}
}
build(ans);
return 1;
}
int sub3(const vvi& p) {
if (!dsu(p)) return 0;
vvi ans(N, vector<int>(N));
vvi groups;
for (int i=0; i<N; ++i) {
if (i == par(i)) {
vector<int> cur;
for (int j=0; j<N; ++j) {
if (i == par(j)) {
cur.push_back(j);
}
}
groups.push_back(cur);
}
}
for (int i=0; i<groups.size(); ++i) {
int gsz = groups[i].size();
if (gsz == 1) continue;
if (gsz == 2) return 0;
for (int j=0; j<gsz; ++j) {
ans[groups[i][(j+1) % gsz]][groups[i][j]] = ans[groups[i][j]][groups[i][(j+1) % gsz]] = 1;
}
}
build(ans);
return 1;
}
int construct(std::vector<std::vector<int>> p) {
N = p.size();
set<int> vals;
for (int i=0; i<N; ++i) {
for (int j=i+1; j<N; ++j) {
vals.insert(p[i][j]);
}
}
if (vals.size() <= 2) {
if (vals.count(1)) {
return sub2(p);
}
if (vals.count(2)) {
return sub3(p);
}
}
return 0;
}
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... |