| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 316364 | demetre | 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;
long long par[300005],a,bb,n,fix[300005],w1,w2,sh1,fix1[300005],wv,par1[300005];
long long pa,sh;
vector <long long> v[300005],v1,v2;
int get_col(int a){
if (par[a]==a) return a;
par[a]=get_col(par[a]);
return par[a];
}
void col(int a, int b){
a=get_col(a);
b=get_col(b);
par[a]=b;
}
int get_col1(int a{
if (par1[a]==a) return a;
par1[a]=get_col1(par1[a]);
return par1[a];
}
void col1(int a, int b){
a=get_col1(a);
b=get_col1(b);
par1[a]=b;
}
int construct(vector <vector <int> > p){
int n=p.size();
for (int i=0; i<n; i++)
par[i]=i;
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
if (p[i][j]==3)
return 0;
}
}
for (int i=0; i<n; i++){
for (int j=0; j<n; j++)
if (p[i][j]) col(i,j);
}
for (int i=0; i<n; i++){
for (int j=0; j<n; j++)
if (get_col(i)==get_col(j) && !p[i][j]) return 0;
}
for (int i=0; i<n;i++)
v[get_col(i)].push_back(i);
for (int i=0; i<n; i++){
if (!fix[get_col(i)])
v1.push_back(get_col(i));
fix[get_col(i)]=1;
}
vector < vector < int > > ans(n, vector < int >(n, 0));
for (int i=0; i<n; i++)
par1[i]=i;
for (int i=0; i<v1.size(); i++){
pa=v1[i];
for(int j=0;j<v[pa].size(); j++){
for (int j1=j+1; j1<v[pa].size(); j1++){
w1=v[pa][j];
w2=v[pa][j1];
if (p[w1][w2]==1)
col1(w1,w2);
}
}
}
for (int i=0; i<v1.size() ;i++){
pa=v1[i];
for(int j=0; j<v[pa].size(); j++){
sh=get_col1(v[pa][j]);
sh1=v[pa][j];
if (sh!=sh1){
ans[sh][sh1]=1;
ans[sh1][sh]=1;
}
}
}
for (int i=0; i<v1.size(); i++){
pa=v1[i];
for (int j=0; j<v[pa].size(); j++){
for (int j1=0; j1<v[pa].size(); j1++){
w1=v[pa][j];
w2=v[pa][j1];
if (p[w1][w2]==2){
if (get_col1(w1)==get_col1(w2)) return 0;
}
}
}
}
for (int i=0; i<v1.size(); i++){
pa=v1[i];
v2.clear();
for (int j=0; j<v[pa].size(); j++){
wv=v[pa][j];
if (!fix1[get_col1(wv)]){
fix1[get_col1(wv)]=1;
v2.push_back(get_col1(wv));
}
}
if (v2.size()==2)
return 0;
v2.push_back(v2[0]);
for (int i=1; i<v2.size(); i++){
w1=v2[i];
w2=v2[i-1];
if (w1!=w2){
ans[w1][w2]=1;
ans[w2][w1]=1;
}
}
}
build(ans);
return 1;
}