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;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
using int64 = long long;
using ld = long double;
constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;
class dsu {
int n;
std::vector<int> e;
int pfind(const int x) {
return (e[x] < 0 ? x : pfind(e[x]));
}
public:
dsu() : n(0), comp(0) {}
explicit dsu(const int n) : n(n), comp(n), e(n, -1) {}
int comp;
int find(const int x) {
assert(0 <= x and x < n);
return pfind(x);
}
bool unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
if (e[x] > e[y]) swap(x, y);
e[x] += e[y];
e[y] = x;
comp--;
return true;
}
bool same(const int x, const int y) {
return (find(x) == find(y));
}
int size(const int x) {
return -e[find(x)];
}
std::vector<std::vector<int>> components() {
std::vector<std::vector<int>> res(n);
for (int x = 0; x < n; x++) {
res[pfind(x)].push_back(x);
}
res.erase(
std::remove_if(res.begin(), res.end(), [&](const std::vector<int> &v) { return v.empty(); }),
res.end());
return res;
}
};
vector<vector<int>> ways;
vector<vector<int>> ans;
void connect(const int x, const int y) {
ans[x][y] = 1;
ans[y][x] = 1;
}
bool connect1(const vector<int> &nodes) {
if (nodes.size() < 2) return false;
for (int i = 0; i < nodes.size() - 1; i++) {
connect(nodes[i], nodes[i + 1]);
}
return true;
}
bool connect2(const vector<int> &nodes) {
if (nodes.size() < 3) return false;
connect1(nodes);
connect(nodes.front(), nodes.back());
return true;
}
bool connect3(const vector<int> &nodes) {
if (nodes.size() < 4) return false;
connect2(nodes);
connect(nodes[0], nodes[2]);
return true;
}
bool solve(const vector<int> &nodes) {
const int n = (int)nodes.size();
bool two = false;
bool three = false;
dsu d(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
const int way = ways[nodes[i]][nodes[j]];
if (way == 1) {
d.unite(i, j);
} else if (way == 2) {
two = true;
} else {
three = true;
}
}
}
if (two and three) return false;
const vector<vector<int>> lines = d.components();
for (auto line : lines) {
for (int i = 0; i < line.size(); i++) {
for (int j = i + 1; j < line.size(); j++) {
const int x = nodes[line[i]];
const int y = nodes[line[j]];
if (ways[x][y] != 1) return false;
}
line[i] = nodes[line[i]];
}
connect1(line);
}
if (lines.size() == 1) return true;
vector<int> cycle;
for (const auto &line : lines) {
cycle.push_back(nodes[d.find(line[0])]);
}
return (two ? connect2(cycle) : connect3(cycle));
}
int construct(vector<std::vector<int>> p) {
const int n = (int) p.size();
ways = p;
dsu d(n);
vector<pair<int, int>> disjoint;
for (int x = 0; x < n; x++) {
for (int y = x + 1; y < n; y++) {
if (p[x][y] == 0) {
disjoint.emplace_back(x, y);
} else {
d.unite(x, y);
}
}
}
for (const auto &[x, y] : disjoint) {
if (d.same(x, y)) return false;
}
ans.assign(n, vector<int>(n));
const auto components = d.components();
for (const auto &component : components) {
if (not solve(component)) return false;
}
build(ans);
return true;
}
Compilation message (stderr)
supertrees.cpp: In constructor 'dsu::dsu(int)':
supertrees.cpp:29:7: warning: 'dsu::comp' will be initialized after [-Wreorder]
29 | int comp;
| ^~~~
supertrees.cpp:19:20: warning: 'std::vector<int> dsu::e' [-Wreorder]
19 | std::vector<int> e;
| ^
supertrees.cpp:27:12: warning: when initialized here [-Wreorder]
27 | explicit dsu(const int n) : n(n), comp(n), e(n, -1) {}
| ^~~
supertrees.cpp: In function 'bool connect1(const std::vector<int>&)':
supertrees.cpp:76:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for (int i = 0; i < nodes.size() - 1; i++) {
| ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp: In function 'bool solve(const std::vector<int>&)':
supertrees.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for (int i = 0; i < line.size(); i++) {
| ~~^~~~~~~~~~~~~
supertrees.cpp:121:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for (int j = i + 1; j < line.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... |