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;
struct DisjointSet {
int n;
vector<int> parent, rank;
DisjointSet(int _n) : n(_n) {
parent.resize(n);
iota(parent.begin(), parent.end(), 0);
rank.resize(n, 0);
}
int find(int u) {
return parent[u] = (u == parent[u] ? u : find(parent[u]));
}
void merge(int u, int v) {
u = find(u); v = find(v);
if (u == v) return;
if (rank[u] > rank[v]) swap(u, v);
parent[u] = v;
if (rank[u] == rank[v]) ++rank[v];
}
};
int construct(vector<vector<int>> p) {
int n = p.size();
for (int i=0; i<n; ++i) {
for (int j=0; j<n; ++j) {
if (p[i][j] == 3) {
return 0;
}
}
}
DisjointSet dsu(n);
DisjointSet dsu2(n);
for (int i=0; i<n; ++i) {
for (int j=0; j<n; ++j) {
if (p[i][j] >= 1) {
dsu.merge(i, j);
}
if (p[i][j] == 1) {
dsu2.merge(i, j);
}
}
}
for (int i=0; i<n; ++i) {
for (int j=0; j<n; ++j) {
if (i != j) {
if (dsu.find(i) == dsu.find(j) && p[i][j] == 0) return 0;
if (dsu2.find(i) == dsu2.find(j) && p[i][j] == 2) return 0;
if (dsu.find(i) == dsu.find(j) && dsu2.find(i) != dsu2.find(j) && p[i][j] != 2) return 0;
}
}
}
vector<vector<int>> ans(n, vector<int>(n, 0));
vector<vector<int>> trees(n);
for (int i=0; i<n; ++i) trees[dsu2.find(i)].push_back(i);
for (int i=0; i<n; ++i) {
// for (int x: trees[i]) cout << x << ' ';
// cout << endl;
for (int j=0; j+1<trees[i].size(); ++j) {
int x = trees[i][j];
int y = trees[i][j+1];
ans[x][y] = ans[y][x] = 1;
}
}
vector<vector<int>> comps(n);
for (int i=0; i<n; ++i) {
if (!trees[i].empty()) {
comps[dsu.find(trees[i][0])].push_back(trees[i][0]);
}
}
for (int i=0; i<n; ++i) {
// for (int x: comps[i]) cout << x << ' ';
// cout << endl;
for (int j=0; j+1<comps[i].size(); ++j) {
int x = comps[i][j];
int y = comps[i][j+1];
ans[x][y] = ans[y][x] = 1;
}
if (comps[i].size() >= 2) ans[comps[i][0]][comps[i].back()] = ans[comps[i].back()][comps[i][0]] = 1;
}
build(ans);
return 1;
}
Compilation message (stderr)
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:65:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for (int j=0; j+1<trees[i].size(); ++j) {
| ~~~^~~~~~~~~~~~~~~~
supertrees.cpp:80:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int j=0; j+1<comps[i].size(); ++j) {
| ~~~^~~~~~~~~~~~~~~~
# | 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... |