| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 600467 | UncoolAnon | 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 <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
const int inf=1e9;
void merge(int i,int j,vector<int>& id,vector<vector<int>>& group){
if(id[i]!=id[j]){
int a=id[i],b=id[j];
if(group[a].size()>group[b].size()) swap(a,b);
for(int&x:group[a]) group[b].push_back(x);
for(int&x:group[a]) id[x]=b;
group[a].clear();
}
return ;
}
void build(vector<vector<int>> p){
for(vector<int>&x:p){
for(int&y:x) cout << y << " ";
cout<<endl;
}
}
int construct(vector<vector<int>> p){
int n=p.size();
vector<vector<int>> group(n),grp(n);
vector<int> id(n),rid(n);
for(int i=0;i<n;i++){
id[i]=i; rid[i]=i;
group[i].push_back(i);
grp[i].push_back(i);
}
vector<vector<int>> answer(n,vector<int>(n,0));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i!=j&&group[id[i]].size()==1&&group[id[j]].size()==1&&p[i][j]==1){
merge(i,j,rid,grp);
}
}
}
for(int i=0;i<n;i++){
for(int&x:grp[i])
for(int&y:grp[i])
if(p[x][y]!=1)
return 0;
for(int&x:grp[i]) if(x!=i) answer[i][x]=answer[x][i]=1;
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
if(rid[i]!=rid[j]&&rid[i]==i&&rid[j]==j){
int zero=0,two=0;
for(int&x:grp[i])
for(int&y:grp[j])
zero+=(p[x][y]==0),two=(p[x][y]==2);
if(zero&&two) return 0;
if(two){
merge(i,j,id,group);
}
}
}
for(int i=0;i<n;i++)
if(group[i].size()>1){
for(int j=0;j<group[i].size();j++)
answer[group[i][j]][group[i][(j+1)%group[i].size()]]=answer[group[i][(j+1)%group[i].size()]][group[i][j]]=1;
}
build(answer);
return 1;
}