| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 651896 | coding_snorlax | Connecting Supertrees (IOI20_supertrees) | C++14 | 0 ms | 0 KiB |
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[1005]={0};
int answer=1;
for(int i=0;i<(int)x.size();i++){
int now_check=query(i);
vector<int> List1={i};
if(!OK_List[i]){
OK_List[i]=1;
for(int j=0;j<(int)x.size();j++){
if(i!=j && now_check==query(j)){
List1.push_back(j);
OK_List[j]=1;
}
}
}
List1.push_back(i);
if((int)List1.size()>3){
for(int k=0;k<(int)List1.size()-1;k++){
built[List1[k]][List1[k+1]]=1;
built[List1[k+1]][List1[k]]=1;
}
}
else{
//cout<<(int)List1.size()<<" "<<List1[0]<<" "<<List1[1]<< " "<<List1[2];
if((int)List1.size()==3) 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,2,2},{2,1,2,2,2},{2,2,1,2,2},{2,2,2,1,2},{2,2,2,2,1}};
construct(x);
}