#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
vector<int> par1(1001),sz1(1001,1),par2(1001),sz2(1001,1),par3(1001),sz3(1003,1);
int findPar1(int u){
if(par1[u]==u) return u;
return par1[u]=findPar1(par1[u]);
}
int findPar2(int u){
if(par2[u]==u) return u;
return par2[u]=findPar2(par2[u]);
}
int findPar3(int u){
if(par3[u]==u) return u;
return par3[u]=findPar3(par3[u]);
}
void unite1(int u,int v){
int ulp=findPar1(u);
int vlp=findPar1(v);
if(ulp==vlp) return;
if(sz1[ulp]>sz1[vlp]){
par1[vlp]=ulp;
sz1[ulp]+=sz1[vlp];
}else{
par1[ulp]=vlp;
sz1[vlp]+=sz1[ulp];
}
}
void unite2(int u,int v){
int ulp=findPar2(u);
int vlp=findPar2(v);
if(ulp==vlp) return;
if(sz2[ulp]>sz2[vlp]){
par2[vlp]=ulp;
sz2[ulp]+=sz2[vlp];
}else{
par2[ulp]=vlp;
sz2[vlp]+=sz2[ulp];
}
}
void unite3(int u,int v){
int ulp=findPar3(u);
int vlp=findPar3(v);
if(ulp==vlp) return;
if(sz3[ulp]>sz3[vlp]){
par3[vlp]=ulp;
sz3[ulp]+=sz3[vlp];
}else{
par3[ulp]=vlp;
sz3[vlp]+=sz3[ulp];
}
}
bool is_samee1(int u,int v){
return findPar1(u)==findPar1(v);
}
bool is_samee2(int u,int v){
return findPar2(u)==findPar2(v);
}
bool is_samee3(int u,int v){
return findPar3(u)==findPar3(v);
}
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> adj(n,vector<int>(n,0));
// subtask 4
for(int i=0;i<n;++i) par1[i]=par2[i]=par3[i]=i;
for(int i=0;i<n;++i){
for(int j=i+1;j<n;++j){
if(p[i][j]==2){
unite2(i,j);
unite3(i,j);
}
}
}
for(int i=0;i<n;++i){
for(int j=i+1;j<n;++j){
if(p[i][j]==1&&sz2[i]==1&&sz2[j]==1){
unite1(i,j);
unite3(i,j);
}
}
}
for(int i=0;i<n;++i){
if(sz2[findPar2(i)]==2) return 0;
for(int j=i+1;j<n;++j){
if(p[i][j]==0&&is_samee3(i,j)) return 0;
}
}
vector<int> last_2(n+1,-1),first(n+1,-1),last_1(n+1,-1);
for(int i=0;i<n;++i){
// connecting the 2 ways road
int ulp1=findPar2(i);
if(last_2[ulp1]!=-1&&sz2[ulp1]>2){
adj[i][last_2[ulp1]]=1;
adj[last_2[ulp1]][i]=1;
}
if(first[ulp1]==-1) first[ulp1]=i;
last_2[ulp1]=i;
ulp1=findPar1(i);
if(last_1[ulp1]!=-1&&sz1[ulp1]>1){
adj[i][last_1[ulp1]]=1;
adj[last_1[ulp1]][i]=1;
}
last_1[ulp1]=i;
}
for(int i=0;i<n;++i){
int ulp=findPar2(i);
if(sz2[ulp]>1) adj[last_2[ulp]][first[ulp]]=adj[first[ulp]][last_2[ulp]]=1;
}
for(int i=0;i<n;++i){
for(int j=i+1;j<n;++j){
if(p[i][j]==1&&!is_samee3(i,j)){
unite3(i,j);
adj[i][j]=adj[j][i]=1;
}
}
}
/*
for(int i=0;i<n;++i){
for(int j=i+1;j<n;++j){
if(adj[i][j]>0){
cout<<i<<" - "<<j<<'\n';
}
}
}*/
build(adj);
return 1;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("input.in","r",stdin);
freopen("output.out","w",stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n,q,u,v,w;cin>>n>>q;
vector<vector<int>> p(n,vector<int>(n,0));
for(int i=0;i<n;++i) p[i][i]=1;
while(q--){
cin>>u>>v>>w;
p[u][v]=p[v][u]=w;
}
construct(p);
//cout<<-1<<'\n';
return 0;
}
Compilation message
supertrees.cpp: In function 'int main()':
supertrees.cpp:160:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
160 | freopen("input.in","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:161:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
161 | freopen("output.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccR3Ptnx.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccEURiZx.o:supertrees.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
