| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 300999 | ElyesChaabouni | 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>
int anc[200000], anc1[200000];
void get_anc(int x)
{
int cu=anc[x];
while(cu!=anc[cu])
cu=anc[cu];
anc[x]=cu;
}
void unite(int x, int y)
{
get_anc(x);
get_anc(y);
anc[anc[y]]=anc[x];
anc[y]=anc[x];
}
void get_anc1(int x)
{
int cu=anc1[x];
while(cu!=anc1[cu])
cu=anc1[cu];
anc1[x]=cu;
}
void unite1(int x, int y)
{
get_anc1(x);
get_anc1(y);
anc1[anc1[y]]=anc1[x];
anc1[y]=anc1[x];
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
std::vector<std::vector<int>> ans;
for (int i = 0; i < n; i++) {
std::vector<int> row;
row.resize(n);
answer.push_back(row);
}
for(int i = 0; i < n; i++)
for(int j 0; j < n; j++)
ans[i][j]=0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(p[i][j]==1)
unite(x, y);
}
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if((get_anc(i)==get_anc(j) && p[i][j]!=1 )||(get_anc(i)!=get_anc(j) && p[i][j]==1 ))
return 0;
if(p[i][j]==3)
return 0;
}
}
for(int i = 0; i < n; i++)
{
vector<int>v;
for(int j = 0; j < n; j++)
{
if(anc[j]==i)
v.push_back(j);
}
for(int j = 0; j < (int)(v.size())-1; j++)
{
ans[v[j]][v[j+1]]=1;
ans[v[j+1]][v[j]]=1;
}
}
for(int i = ; i < n; i++)
anc1[j]=-1;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(p[i][j]==2)
{
unite1(get_anc(i), get_anc(j));
}
}
}
for(int i = 0; i < n; i++)
{
vector<int>v;
for(int j = 0; j < n; j++)
{
if(anc1[j]==i)
v.push_back(j);
}
for(int j = 0; j < (int)(v.size())-1; j++)
{
ans[v[j]][v[j+1]]=1;
ans[v[j+1]][v[j]]=1;
}
if(v.size() == 2)
return 0;
ans[v[0]][v[n-1]]=1;
ans[v[n-1]][v[0]]=1;
}
build(ans);
return 1;
}