#include<bits/stdc++.h>
#include "supertrees.h"
#define ll int
#define in insert
#define pb push_back
#define vl vector<ll>
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;
struct DSU{
vl par;
vector<vector<ll>> e;
void init(ll n){
e.resize(n + 1);
par.resize(n + 1);
ll i;
for(i = 0; i < n; i++){
e[i].pb(i);
par[i] = i;
}
}
ll get(ll x){
if(par[x] == x){
return x;
}
return par[x] = get(par[x]);
}
bool connected(ll x, ll y){
return (get(x) == get(y));
}
bool unite(ll a, ll b){
a = get(a);
b = get(b);
if(a == b){return false;}
if(e[a].size() < e[b].size()){
swap(a, b);
}
par[b] = a;
for(auto x: e[b]){
e[a].pb(x);
par[x] = a;
}
e[b].clear();
return true;
}
};
int construct(vector<vector<int>> p) {
DSU dsu1, dsu2;
ll n = p.size(), i, j;
dsu1.init(n);
dsu2.init(n);
vector<vector<ll>> ans(n, vector<ll> (n, 0));
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
if(p[i][j] == 1){
dsu1.unite(i, j);
}
}
}
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
if(p[i][j] != 1 && dsu1.connected(i, j)){
//cout << "1" << endl;
return 0;
}
}
}
// for(i = 0; i < n; i++){cout << dsu1.get(i) << ' ';}cout << endl;
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
if(p[i][j] == 2){
if(dsu2.unite(dsu1.get(i), dsu1.get(j))){
// cout << dsu1.get(i) << ' ' << dsu1.get(j) << endl;
}
}
}
}
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
if(i == j){continue;}
if(p[i][j] != 2 && dsu2.connected(i, j)){
//cout << "2" << endl;
return 0;
}
}
}
vector<bool> used(n, 0), vis(n, 0);
for(i = 0; i < n; i++){
ll x = dsu2.get(i);
if(dsu2.e[x].size() == 2){/*cout << "3" << endl;*/return 0;}
if(dsu2.e[x].size() > 2 && !used[x]){
for(j = 0;j < dsu2.e[x].size() - 1; j++){
ans[dsu2.e[x][j]][dsu2.e[x][j + 1]] = 1;
ans[dsu2.e[x][j + 1]][dsu2.e[x][j]] = 1;
}
ans[dsu2.e[x][0]][dsu2.e[x].back()] = ans[dsu2.e[x].back()][dsu2.e[x][0]] = 1;
used[x] = 1;
}
x = dsu1.get(i);
if(dsu1.e[x].size() < 2){continue;}
if(!vis[x]){
for(j = 0;j < dsu1.e[x].size() - 1; j++){
ans[dsu1.e[x][j]][dsu1.e[x][j + 1]] = 1;
ans[dsu1.e[x][j + 1]][dsu1.e[x][j]] = 1;
}
ans[dsu1.e[x][0]][dsu1.e[x].back()] = ans[dsu1.e[x].back()][dsu1.e[x][0]] = 1;
vis[x] = 1;
}
}
build(ans);
return 1;
}
/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1
*/
Compilation message
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:94:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(j = 0;j < dsu2.e[x].size() - 1; j++){
| ~~^~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:104:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(j = 0;j < dsu1.e[x].size() - 1; j++){
| ~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Incorrect |
1 ms |
344 KB |
Too many ways to get from 0 to 2, should be 1 found no less than 2 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Incorrect |
1 ms |
344 KB |
Too many ways to get from 0 to 2, should be 1 found no less than 2 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
7 ms |
1372 KB |
Output is correct |
9 |
Correct |
154 ms |
24072 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
7 ms |
1428 KB |
Output is correct |
13 |
Correct |
156 ms |
24068 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
3 ms |
860 KB |
Output is correct |
17 |
Correct |
82 ms |
14204 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
600 KB |
Output is correct |
21 |
Correct |
39 ms |
6264 KB |
Output is correct |
22 |
Correct |
157 ms |
24052 KB |
Output is correct |
23 |
Correct |
159 ms |
24196 KB |
Output is correct |
24 |
Correct |
161 ms |
24148 KB |
Output is correct |
25 |
Correct |
65 ms |
14160 KB |
Output is correct |
26 |
Correct |
64 ms |
14336 KB |
Output is correct |
27 |
Correct |
155 ms |
24164 KB |
Output is correct |
28 |
Correct |
179 ms |
24312 KB |
Output is correct |
29 |
Correct |
62 ms |
14164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Incorrect |
1 ms |
348 KB |
Too many ways to get from 1 to 4, should be 1 found no less than 2 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Incorrect |
1 ms |
344 KB |
Too many ways to get from 0 to 2, should be 1 found no less than 2 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Incorrect |
1 ms |
344 KB |
Too many ways to get from 0 to 2, should be 1 found no less than 2 |
4 |
Halted |
0 ms |
0 KB |
- |