//#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"
const int N = 2e5 + 9 , mod = 1e9 + 7;
ll a[N] , b[N] , dp[N];
//int press(string a){}
int construct(vector<vector<int>> v){
ll i , j , l , r , s = 0, f , n , m , x , y , k;
n = v.size();
vector<vector<int>>c(n);
for(i = 0; i < n; i++)
c[i].resize(n);
for(i = 0; i < n; i++){
if(b[i] != 0)
continue;
vector<pair<int,pair<int,int>>>vc;
vector<int>v1 , v2 , v3;
for(j = 0; j < n; j++)
if(v[i][j] != 0){
b[j] = 1 , v1.pb(j);
}
l = r = 0;
for(x = 0; x < v1.size(); x++){
if(b[v1[x]] != 2)
b[v1[x]] = 3;
f = v1[x];
vector<int>vv;
vv.pb(f);
for(y = x + 1; y < v1.size(); y++){
vc.pb({v[v1[x]][v1[y]] , {v1[x] , v1[y]}});
if(v[v1[x]][v1[y]] == 2)
l = 1;
else if(v[v1[x]][v1[y]] == 3)
r = 1;
else if(b[v1[x]] == 3){
if(b[v1[y]] == 2)
return 0;
c[v1[y]][f] = c[f][v1[y]] = 1;
b[v1[y]] = 2;
f = v1[y];
vv.pb(f);
}
}
if(b[v1[x]] == 3)
for(auto to : vv){
s= 0;
for(auto to1:vv)
if(v[to][to1] != 1)
return 0;
for(j = 0; j < n; j++)
if(v[to][j] == 1)
s++;
if(s != vv.size())
return 0;
}
}
sort(all(vc));
if(v1.size() == 1)
continue;
if((l == 1 && r == 1) || vc.front().fi == 0)
return 0;
set<int>st;
for(auto to : v1){
st.insert(to);
if(b[to] == 3)
v2.pb(to);
else
v3.pb(to);
}
if(l + r > 0){
if(v2.size() <= vc.back().fi){
return 0;
}
f = v2.back();
for(auto to : v2)
c[f][to] = c[to][f] = 1 , f = to;
if(vc.back().fi == 3)
c[v2[0]][v2[2]] = c[v2[2]][v2[0]] = 1;
}
for(auto to : v1){
ll L = 0 ,R = 0 , s =0;
for(j = 0; j < n ; j++)
if(v[to][j] != 0){
if(st.find(j) == st.end())
return 0;
s++;
if(to == j)
continue;
if(v[to][j] == 2)
L = 1;
else if(v[to][j] == 3)
R = 1;
else {
// if(b[to] == 1 || b[j] == 1)
// return 0;
}
}
if((L > l) || (R > r) || s != v1.size())
return 0;
}
}
// for(i = 0; i < n; i++){
// for(j = 0; j < n; j++)
// cout<<c[i][j]<<" ";
// cout<<"\n";
// }
build(c);
return 1;
}
/*
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cout<<construct({{1, 1, 2, 2}, {1, 1, 2, 2}, {2, 2, 1, 2}, {2, 2, 2, 1}});
}*/
// Author : حسن
Compilation message
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:42:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(x = 0; x < v1.size(); x++){
| ~~^~~~~~~~~~~
supertrees.cpp:48:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(y = x + 1; y < v1.size(); y++){
| ~~^~~~~~~~~~~
supertrees.cpp:72:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | if(s != vv.size())
| ~~^~~~~~~~~~~~
supertrees.cpp:90:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
90 | if(v2.size() <= vc.back().fi){
| ^
supertrees.cpp:117:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | if((L > l) || (R > r) || s != v1.size())
| ~~^~~~~~~~~~~~
supertrees.cpp:126:5: error: 'build' was not declared in this scope
126 | build(c);
| ^~~~~
supertrees.cpp:27:40: warning: unused variable 'm' [-Wunused-variable]
27 | ll i , j , l , r , s = 0, f , n , m , x , y , k;
| ^
supertrees.cpp:27:52: warning: unused variable 'k' [-Wunused-variable]
27 | ll i , j , l , r , s = 0, f , n , m , x , y , k;
| ^
