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>
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(all(x))
#define press(x) x.erase(unique(all(x)), x.end());
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
typedef pair<LL, LL> pll;
const int INF=1e9;
const LL LLINF=1e18;
int n, arr[1010][1010], ans[1010][1010], tnum[1010];
struct UNION_FIND{
int par[1010];
UNION_FIND(){for(int i=1; i<=1000; i++)par[i]=i;}
int findpar(int a){return a==par[a]?a:par[a]=findpar(par[a]);}
void mergepar(int a, int b){par[findpar(a)]=findpar(b);}
}cyc, tree;
vector<int> rt[1010];
int construct(vector<vector<int> > p){
n=p.size();
for(int i=0; i<n; i++){
for(int j=0; j<n; j++)arr[i+1][j+1]=p[i][j];
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(arr[i][j]==3)return 0;
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(arr[i][j]==1&&i!=j)tree.mergepar(i, j);
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(tree.findpar(i)==tree.findpar(j)&&arr[i][j]!=1)return 0;
}
}
for(int i=1; i<=n; i++)tnum[i]=tree.findpar(i);
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(arr[i][j]==2)cyc.mergepar(tnum[i], tnum[j]);
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(tnum[i]==tnum[j])continue;
if(cyc.findpar(tnum[i])==cyc.findpar(tnum[j])&&arr[i][j]!=2)return 0;
}
}
for(int i=1; i<=n; i++){
rt[cyc.findpar(tnum[i])].eb(tnum[i]);
if(i==tnum[i])continue;
ans[i][tnum[i]]=1;
ans[tnum[i]][i]=1;
}
for(int i=1; i<=n; i++){
svec(rt[i]);
press(rt[i]);
if(rt[i].size()<=1)continue;
for(int j=0; j<rt[i].size()-1; j++){
ans[rt[i][j]][rt[i][j+1]]=1;
ans[rt[i][j+1]][rt[i][j]]=1;
}
ans[rt[i][0]][rt[i].back()]=1;
ans[rt[i].back()][rt[i][0]]=1;
}
vector<vector<int> > ret;
for(int i=1; i<=n; i++){
vector<int> vc;
vc.resize(n);
for(int j=1; j<=n; j++){
if(ans[i][j])vc[j-1]=1;
}
ret.push_back(vc);
}
build(ret);
return 1;
}
Compilation message (stderr)
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int j=0; j<rt[i].size()-1; j++){
| ~^~~~~~~~~~~~~~~
# | 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... |