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;
int Boss[1005];
int Rank[1005];
int query(int x){
if(Boss[x]==x) return x;
else return Boss[x]=query(Boss[x]);
}
int Union(int x,int y){
int A1=query(x);
int A2=query(y);
if(A1==A2){
return 0;
}
if (Rank[A1]>Rank[A2]) Boss[A2]=A1;
else if(Rank[A1]<Rank[A2]) Boss[A1]=A2;
else{
Boss[A2]=A1;
Rank[A1]++;
}
return 1;
}
int build(vector<vector<int>> x){
for(int i=0;i<x.size();i++){
for(int j=0;j<x.size();j++){
cout<<x[i][j]<<" ";
}
cout<<endl;
}
}
int construct(vector<vector<int>> x){
for(int i=0;i<1005;i++){
Boss[i]=i;
Rank[i]=0;
}
vector<vector<int>> built;
for(int i=0;i<x.size();i++){
vector<int> New;
for(int j=0;j<x.size();j++){
New.push_back(0);
}
built.push_back(New);
}
int check=0;
for(int i=0;i<x.size();i++){
for(int j=0;j<x.size();j++){
if (x[i][j]){
check=Union(i,j);
/*
if(check && i!=j){
built[i][j]=1;
built[j][i]=1;
*/
}
}
}
int OK_List[1000]={1};
int answer=1;
for(int i=0;i<x.size();i++){
int now_check=Boss[i];
vector<int> List1={i};
if(OK_List[i]){
OK_List[i]=0;
for(int j=0;j<x.size();j++){
if(i!=j && now_check==Boss[j]){
List1.push_back(j);
OK_List[j]=0;
}
}
}
List1.push_back(i);
if(List1.size()>3){
for(int k=0;k<List1.size()-1;k++){
built[List1[k]][List1[k+1]]=1;
built[List1[k+1]][List1[k]]=1;
}
}
else{
answer=0;
}
}
for(int i=0;i<x.size();i++){
for(int j=i+1;j<x.size();j++){
if ((x[i][j] && query(i)!=query(j)) || (!x[i][j] && query(i)==query(j))){
answer=0;
}
}
}
if(answer) build(built);
return answer;
}
int main(){
vector<vector<int>> x={{1,2,2,0,0},{2,1,2,0,0},{2,2,1,0,0},{0,0,0,1,2},{0,0,0,2,1}};
construct(x);
}
Compilation message (stderr)
supertrees.cpp: In function 'int build(std::vector<std::vector<int> >)':
supertrees.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(int i=0;i<x.size();i++){
| ~^~~~~~~~~
supertrees.cpp:26:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for(int j=0;j<x.size();j++){
| ~^~~~~~~~~
supertrees.cpp:31:1: warning: no return statement in function returning non-void [-Wreturn-type]
31 | }
| ^
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:38:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i=0;i<x.size();i++){
| ~^~~~~~~~~
supertrees.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int j=0;j<x.size();j++){
| ~^~~~~~~~~
supertrees.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i=0;i<x.size();i++){
| ~^~~~~~~~~
supertrees.cpp:47:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int j=0;j<x.size();j++){
| ~^~~~~~~~~
supertrees.cpp:61:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i=0;i<x.size();i++){
| ~^~~~~~~~~
supertrees.cpp:66:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int j=0;j<x.size();j++){
| ~^~~~~~~~~
supertrees.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int k=0;k<List1.size()-1;k++){
| ~^~~~~~~~~~~~~~~
supertrees.cpp:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int i=0;i<x.size();i++){
| ~^~~~~~~~~
supertrees.cpp:85:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int j=i+1;j<x.size();j++){
| ~^~~~~~~~~
supertrees.cpp:45:9: warning: variable 'check' set but not used [-Wunused-but-set-variable]
45 | int check=0;
| ^~~~~
/usr/bin/ld: /tmp/cclWT3Wt.o: in function `build(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >)':
grader.cpp:(.text+0x320): multiple definition of `build(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >)'; /tmp/ccXd8Z4s.o:supertrees.cpp:(.text+0x1b0): first defined here
/usr/bin/ld: /tmp/cclWT3Wt.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccXd8Z4s.o:supertrees.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status