이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int head[1005],sz[1005];
vector<int>groups[1005],lines[1005];
int find(int node){
return head[node]=(node==head[node]?node:find(head[node]));
}
void combine(int i,int j){
int a=find(i);
int b=find(j);
if(a==b) return;
if(sz[a]>sz[b]){
head[b]=a;
sz[a]+=sz[b];
}
else{
head[a]=b;
sz[b]+=sz[a];
}
}
int construct(vector<vector<int> >p) {
// cout << "LOL" << '\n';
int n = p.size();
vector<vector<int> > ans;
for (int i = 0; i < n; i++) {
vector<int> row;
row.resize(n);
ans.push_back(row);
}
for(int i=0;i<n;i++){
head[i]=i;
sz[i]=1;
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(p[i][j]==3) return 0;
if(p[i][j]>0){
combine(i,j);
}
}
}
for(int i=0;i<n;i++){
groups[find(i)].push_back(i);
}
for(int i=0;i<n;i++){
head[i]=i;
sz[i]=1;
}
for(int i=0;i<n;i++){
int szz=groups[i].size();
// cout << szz << '\n';
for(int j=0;j<szz;j++){
for(int k=0;k<szz;k++){
int a=groups[i][j];
int b=groups[i][k];
if(p[a][b]==0) return 0;
if(p[a][b]==1) combine(a,b);
}
}
for(int j=0;j<szz;j++){
int node=groups[i][j];
lines[find(node)].push_back(node);
// cout << node << ' ' << find(node) << '\n';
}
vector<int>cycle;
for(int j=0;j<szz;j++){
int node=groups[i][j];
int szzz=lines[node].size();
if(szzz) cycle.push_back(lines[node][0]);
for(int k=0;k<szzz;k++){
for(int g=0;g<szzz;g++){
int a=lines[node][k];
int b=lines[node][g];
if(p[a][b]==2) return 0;
}
}
for(int k=1;k<szzz;k++){
int a=lines[node][k];
int b=lines[node][k-1];
ans[a][b]=1;
ans[b][a]=1;
}
}
int szzzz=cycle.size();
if(szzzz==2) return 0;
for(int j=0;j<szzzz;j++){
int a=cycle[j];
int b=cycle[(j-1+szzzz)%szzzz];
ans[a][b]=1;
ans[b][a]=1;
}
}
build(ans);
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... |