#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
using ll = long long;
ll n, m, q, k, x, y, a, b, c;
struct dsu {
ll n;
vector<ll> par;
vector<ll> sz;
dsu(ll N) : n(N) {
par.resize(n);
sz.resize(n);
for (int i = 0; i < n; i++) {
par[i] = i;
sz[i] = 1;
}
}
ll find_p(ll x) {
if (par[x] == x) {
return x;
}
ll p = find_p(par[x]);
par[x] = p;
return p;
}
void join(ll x, ll y) {
x = find_p(x);
y = find_p(y);
if (x == y) {
return;
}
if (sz[y] > sz[x]) {
swap(x, y);
}
par[y] = x;
sz[x] += sz[y];
}
};
int construct(vector< vector<int> > p) {
n = p.size();
vector< vector<int> > ans(n, vector<int>(n));
vector< vector<ll> > comp(n);
vector< vector<ll> > comp2(n);
dsu d(n);
bitset<1000> bt;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (p[i][j] == 1) {
d.join(i, j);
bt.set(i);
bt.set(j);
}
}
}
for (int i = 0; i < n; i++) {
if (!bt[i]) {
continue;
}
comp[d.find_p(i)].push_back(i);
}
for (auto i : comp) { // verified
for (int j : i) {
for (int k : i) {
if (p[j][k] != 1) {
return 0;
}
}
}
}
for (auto i : comp) {
if (i.size() <= 1) {
continue;
}
for (int j = 0; j < i.size() - 1; j++) {
ans[i[(j + 1) % i.size()]][i[j]] = 1;
ans[i[j]][i[(j + 1) % i.size()]] = 1;
}
}
for (int i = 0; i < n; i++) {
set<ll> st2;
for (int j : comp[i]) {
for (int k = 0; k < n; k++) {
if (p[j][k] == 2) {
if (bt[k]) {
return 0;
}
st2.insert(k);
}
}
}
// cout << i << ' ' << st2.size() << '\n';
for (int j : st2) {
comp2[i].push_back(j);
bt.set(j);
}
}
// for (auto i : comp2) {
// if (i.size() == 1) {
// return 0;
// }
// for (int j : i) {
// for (int k : i) {
// if (j != k && p[j][k] != 2) {
// return 0;
// }
// }
// }
// }
for (auto i = 0; i < n; i++) {
for (int j : comp[i]) {
for (int k : comp2[i]) {
if (p[j][k] != 2) { // verified
return 0;
}
}
}
}
// cout << "DEBUG" << endl;
for (auto i = 0; i < n; i++) {
if (comp2[i].size() == 0) {
continue;
}
comp2[i].push_back(i);
for (int j = 0; j < comp2[i].size(); j++) {
ans[comp2[i][(j + 1) % comp2[i].size()]][comp2[i][j]] = 1;
ans[comp2[i][j]][comp2[i][(j + 1) % comp2[i].size()]] = 1;
}
}
vector< vector<ll> > comp2i(n);
dsu d2(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (bt[i] && !bt[j] && p[i][j] != 0) { // verified
return 0;
}
if (!bt[i] && bt[j] && p[i][j] != 0) { // verified
return 0;
}
if (!bt[i] && !bt[j] && p[i][j] == 2) {
d2.join(i, j);
}
}
}
for (int i = 0; i < n; i++) {
comp2i[d2.find_p(i)].push_back(i);
}
for (auto i : comp2i) {
if (i.size() == 2) { // verified
return 0;
}
for (int j : i) {
for (int k : i) {
if (p[j][k] != 2) { // verified
return 0;
}
}
}
}
for (auto i : comp2i) {
if (i.size() == 1) {
continue;
}
for (int j = 0; j < i.size(); j++) {
ans[i[(j + 1) % i.size()]][i[j]] = 1;
ans[i[j]][i[(j + 1) % i.size()]] = 1;
}
}
build(ans);
return 1;
}
Compilation message
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:81:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for (int j = 0; j < i.size() - 1; j++) {
| ~~^~~~~~~~~~~~~~
supertrees.cpp:131:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for (int j = 0; j < comp2[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:170:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
170 | for (int j = 0; j < i.size(); j++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
