| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 716427 | Baytoro | Connecting Supertrees (IOI20_supertrees) | C++17 | 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 "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
struct DSU{
vector<int> p,sz;
void build(int n){
p.resize(n);
sz.resize(n);
for(int i=0;i<n;i++){
p[i]=i;
sz[i]=1;
}
}
int f(int x){
if(p[x]==x) return x;
return p[x]=f(p[x]);
}
void add_edge(int a, int b){
a=f(a);b=f(b);
if(a==b) return;
if(sz[a]>sz[b]) swap(a,b);
p[a]=b;
sz[b]+=sz[a];
}
};
int construct(vector<vector<int>> p) {
int n = p.size();
DSU trees,comp;
trees.build(n);comp.build(n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(p[i][j]==3) return 0;
if(p[i][j]==1)
trees.add_edge(i,j);
if(p[i][j]>0)
comp.add_edge(i,j);
}
}
for(int i=0;i<n && 0;i++){
for(int j=0;j<n;j++){
if(p[i][j]==0 && comp.f(i)!=comp.f(j)) return 0;
if(p[i][j]!=0 && comp.f(i)==comp.f(j)) return 0;
if(p[i][j]==1 && trees.f(i)!=trees.f(j)) return 0;
if(p[i][j]!=1 && trees.f(i)==trees.f(j)) return 0;
if(p[i][j]==2 && comp.f(i)!=comp.f(j) && trees.f(i)==trees.f(j)) return 0;
if(p[i][j]!=2 && comp.f(i)==comp.f(j) && trees.f(i)!=trees.f(j)) return 0;
}
}
vector<int> used(n);
vector<vector<int>> b(n,vector<int>(n,0));
vector<vector<int>> v(n);
for(int i=0;i<n;i++){
if(!used[i]){
used[i]=1;
v[comp.f(i)].push_back(i);
for(int j=0;j<n;j++){
if(j!=i && trees.f(i)==trees.f(j)){
b[i][j]=b[j][i]=1;
used[j]=1;
}
}
}
}
for(auto it: v){
if(it.size()==2) return 0;
if(it.size()>2){
for(int i=0;i<(int)it.size();i++){
b[it[i]][(it[(i+1)%(int)it.size()])]=b[(it[(i+1)%(int)it.size()])][it[i]]=1;
}
}
}
build(b);
return 1;
}