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 <bits/stdc++.h>
#ifndef SKY
#include "supertrees.h"
#endif // SKY
using namespace std;
#define N 1010
#define ll long long
#define fs first
#define sc second
#define ii pair<int,int>
#define pb push_back
int n,ktr[N];
#ifdef SKY
void build(vector<vector<int>>kq)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)cout<<kq[i][j]<<" ";cout<<endl;
}
}
#endif // SKY
struct DSU
{
int lab[N];
vector<int>lis[N];
void init()
{
memset(lab,-1,sizeof(lab));
for(int i=0;i<n;i++)
lis[i].pb(i);
}
int root(int u)
{
if(lab[u]<0)
return u;
return(lab[u]=root(lab[u]));
}
bool update(int u,int v)
{
if((u=root(u))==(v=root(v)))
return 0;
if(lab[u]>lab[v])
swap(u,v);
lab[u]+=lab[v];
lab[v]=u;
for(auto x:lis[v])
lis[u].pb(x);
return 1;
}
}T,D;
int construct(vector<vector<int>> p)
{
n=p[0].size();
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(p[i][j]==3)
return 0;
T.init();
D.init();
vector<vector<int>>kq;
kq.resize(n,vector<int>(n,0));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(p[i][j]==1)
{
if(T.update(i,j)&&D.update(i,j))
kq[i][j]=kq[j][i]=1;
}
for(int i=0;i<n;i++)
{
D.lis[i].clear();
if(D.root(i)==i)
D.lis[i].pb(i);
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(p[i][j]==2)
{
D.update(i,j);
}
//for(int i=0;i<n;i++)cout<<T.root(i)<<" "<<D.root(i)<<endl;
for(int i=0;i<n;i++)
if(D.root(i)==i&&D.lis[i].size()>1)
{
vector<int>s=D.lis[i];
if(s.size()==2)
return 0;
kq[s[0]][s.back()]=kq[s.back()][s[0]]=1;
for(int i=1;i<s.size();i++)
kq[s[i-1]][s[i]]=kq[s[i]][s[i-1]]=1;
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(p[i][j]==0)
{
if(D.root(i)==D.root(j))
return 0;
}
if(p[i][j]==1)
{
if(!(T.root(i)==T.root(j)&&D.root(i)==D.root(j)))
return 0;
}
if(p[i][j]==2)
{
if(!(T.root(i)!=T.root(j)&&D.root(i)==D.root(j)))
return 0;
}
}
build(kq);
return 1;
}
#ifdef SKY
int main()
{
freopen("A.inp","r",stdin);
freopen("A.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin>>n;
vector<vector<int>>p;
p.resize(n,vector<int>(n,0));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>p[i][j];
cout<<construct(p);
return 0;
}
#endif
Compilation message (stderr)
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:99:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int i=1;i<s.size();i++)
| ~^~~~~~~~~
# | 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... |