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;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(),v.end()
#define SZ(a) ((int)a.size())
#define pb push_back
int boss[1005];
vector<int> cpn[1005],tree[1005];
vector<vector<int>> answer;
int finds(int x)
{
if(x==boss[x]) return boss[x];
return boss[x]=finds(boss[x]);
}
void Union(int x,int y)
{
x=finds(x),y=finds(y);
boss[y]=x;
}
void add_edge(int a,int b)
{
answer[a][b]=answer[b][a]=1;
}
int construct(vector<vector<int>> p) {
int n = p.size();
answer=vector<vector<int>>(n,vector<int>(n,0));
vector<int> head;
for(int i=0;i<n;++i)
boss[i]=i;
for(int i=0;i<n;++i)
for(int j=i+1;j<n;++j)
if(p[i][j]>0)
Union(i,j);
for(int i=0;i<n;++i)
for(int j=i+1;j<n;++j)
if(finds(i)==finds(j)&&p[i][j]==0)
return 0;
else if(finds(i)!=finds(j)&&p[i][j]>0)
return 0;
for(int i=0;i<n;++i)
cpn[finds(i)].pb(i);
for(int i=0;i<n;++i)
if(!cpn[i].empty())
{
vector<int> head;
for(int j:cpn[i])
boss[j]=j;
for(int j=0;j<SZ(cpn[i]);++j)
for(int k=j+1;k<SZ(cpn[i]);++k)
if(p[j][k]==1)
Union(j,k);
for(int j=0;j<SZ(cpn[i]);++j)
for(int k=j+1;k<SZ(cpn[i]);++k)
if(finds(j)==finds(k)&&p[j][k]!=1)
return 0;
else if(finds(j)!=finds(k)&&p[j][k]!=2)
return 0;
for(int j:cpn[i])
tree[finds(j)].pb(j);
for(int j:cpn[i])
if(!tree[j].empty())
{
head.pb(tree[j][0]);
for(int k=1;k<SZ(tree[j]);++k)
add_edge(tree[j][k-1],tree[j][k]);
}
for(int i=1;i<SZ(head);++i)
add_edge(head[i-1],head[i]);
if(SZ(head)>1)
add_edge(head[0],head.back());
}
build(answer);
return 1;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |