| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1235867 | stanirina | Connecting Supertrees (IOI20_supertrees) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
vector<vector<int>> g1;
vector<vector<int>> g2;
vector<bool> vis;
vector<int> col;
vector<vector<int>> cmp;
vector<vector<int>> cmp2;
vector<bool> pravicvor;
void dfs(int c,int color){
if(vis[c])return;
col[c]=color;
vis[c]=true;
for(auto a:g1[c]){
if(vis[a])continue;
dfs(a,color);
}
}
void dfs2(int c,int color){
if(vis[c])return;
col[c]=color;
vis[c]=true;
for(auto a:g2[c]){
if(vis[a])continue;
dfs2(a,color);
}
}
void build(vector<vector<int>> ans){
int n=ans.size();
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)cout<<ans[i][j]<<' ';
cout<<endl;
}
}
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> ans(n);
for(int i=0;i<n;i++)ans[i].assign(n,0);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(p[i][j]==3)return 0;
}
}
//cout<<"PRVA PROVERA"<<endl;
g1.resize(n);
for(int i=0;i<n;i++)g1[i].clear();
vis.assign(n,false);
col.assign(n,-1);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j)continue;
if(p[i][j]==1)g1[i].push_back(j);
}
}
for(int i=0;i<n;i++){
if(col[i]!=-1)continue;
vis.assign(n,false);
dfs(i,i);
}
cmp.resize(n);
for(int i=0;i<n;i++)cmp[i].clear();
for(int i=0;i<n;i++)cmp[col[i]].push_back(i);
for(int i=0;i<n;i++){ //provera za jedinice
for(int j=0;j<cmp[i].size();j++){
for(int k=j+1;k<cmp[i].size();k++){
if(p[cmp[i][j]][cmp[i][k]]!=1)return 0;
}
}
}
//cout<<"DRUGA PROVERA"<<endl;
for(int i=0;i<n;i++){ //provera za jedinice
for(int j=1;j<cmp[i].size();j++){
for(int k=0;k<n;k++){
if(k==cmp[i][0] || k==cmp[i][j])continue;
if(p[cmp[i][0]][k]!=p[cmp[i][j]][k])return 0;
}
}
}
//cout<<"TRECA PROVERA"<<endl;
pravicvor.assign(n,false); //poslednji deo drugog koraka
for(int i=0;i<n;i++){
if(cmp[i].size()==0)continue;
pravicvor[cmp[i][0]]=true;
for(int j=1;j<cmp[i].size();j++){
ans[ cmp[i][0] ][ cmp[i][j] ]=1;
ans[ cmp[i][j] ][ cmp[i][0] ]=1;
}
}
///TRECI KORAK
//cout<<"TRECI KORAK"<<endl;
g2.resize(n);
for(int i=0;i<n;i++)g2[i].clear();
vis.assign(n,false);
col.assign(n,-1);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(!pravicvor[i])continue;
if(!pravicvor[j])continue;
if(p[i][j]==2)g2[i].push_back(j);
}
}
for(int i=0;i<n;i++){
if(col[i]!=-1)continue;
if(!pravicvor[i])continue;
vis.assign(n,false);
dfs2(i,i);
}
//cout<<"ZAVRSEN DFS"<<endl;
cmp2.resize(n);
for(int i=0;i<n;i++)cmp2[i].clear();
for(int i=0;i<n;i++){
if(col[i]==-1 || !pravicvor[i])continue;
cmp2[col[i]].push_back(i);
}
for(int i=0;i<n;i++){
if(cmp2[i].size()==0 || cmp2[i].size()==1)continue;
if(cmp2[i].size()<3)return 0;
for(int j=0;j<cmp2[i].size()-1;j++){
ans[ cmp2[i][j+1] ][ cmp2[i][j] ]=1;
ans[ cmp2[i][j] ][ cmp2[i][j+1] ]=1;
}
ans[ cmp2[i][0] ][ cmp2[i][cmp2[i].size()-1] ]=1;
ans[ cmp2[i][cmp2[i].size()-1] ][ cmp2[i][0] ]=1;
}
//cout<<"CETVRTA PROVERA"<<endl;
build(ans);
return 1;
}