이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "supertrees.h"
#define N 1009
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define sz() size()
#define pb push_back
#define pp() pop_back()
using namespace std;
int n, sz[N], p[N];
vector<vector<int>>c;
int vis[N][N];
vector<pii>a;
vector<pii>b;
int vl[N];
/*
void build(vector<vector<int>>m){
for(int i=0; i<m.sz(); i++){
for(int j=0; j<m[i].sz(); j++)
cout<<m[i][j]<<' ';
cout<<'\n';
}
}
*/
int ata(int x){
if(p[x]==x)
return x;
return p[x]=ata(p[x]);
}
void dsu(int x, int y){
x=ata(x);
y=ata(y);
if(sz[y]>sz[x])
swap(x, y);
sz[x]+=sz[y];
p[y]=x, sz[y]=0;
return;
}
int construct(vector<vector<int>>v){
n=v.sz();
c.resize(n);
for(int i=0; i<n; i++)
sz[i]=1, p[i]=i, vl[i]=-1;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
c[i].pb(0);
if(v[i][j]==2)
a.pb({i, j}), v[j][i]=3;
if(v[i][j]==0)
b.pb({i, j});
}
}
for(auto i:a)
if(ata(i.ff)!=ata(i.ss))
dsu(i.ff, i.ss);
int asd=0;
for(auto i:a)
if(ata(i.ff)!=ata(i.ss))
dsu(i.ff, i.ss);
for(auto i:b)
if(ata(i.ff)==ata(i.ss))
asd=1;
for(auto i:a)
if(sz[ata(i.ff)]<3)
asd=1;
if(asd)
return 0;
for(int i=0; i<n; i++){
if(sz[ata(i)]>1){
if(vl[p[i]]>=0)
c[vl[p[i]]][i]=c[i][vl[p[i]]]=1;
vl[p[i]]=i;
}
}
for(int i=0; i<n; i++)
if(vl[p[i]]>=0)
c[vl[p[i]]][i]=c[i][vl[p[i]]]=1, vl[p[i]]=-1;
build(c);
return 1;
}
/*
int main(){
int dsa, qwe;
vector<vector<int>>v;
cin>>dsa;
v.resize(dsa);
for(int i=0; i<dsa ;i++)
for(int j=0; j<dsa; j++)
cin>>qwe, v[i].pb(qwe);
construct(v);
}
*/
# | 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... |