| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 842020 | 8pete8 | 슈퍼트리 잇기 (IOI20_supertrees) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
//#include "supertrees.h"
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define pb push_back
#define all(x) x.begin(),x.end()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
const int mxn=2*1e3,mod=998244353,lg=42,root=80,inf=1e9;
void setIO(string name) {
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
int last[mxn+10],first[mxn+10];
struct dsu{
int pa[mxn+10],sz[mxn+10];
void init(){for(int i=0;i<=mxn;i++)pa[i]=i,sz[i]=1;}
int find(int u){
if(pa[u]==u)return u;
return pa[u]=find(pa[u]);
}
void merg(int u,int v){
int a=find(u),b=find(v);
if(a==b)return;
if(sz[a]>=sz[b]){
pa[b]=a;
sz[a]+=sz[b];
return;
}
pa[a]=b;
sz[b]+=sz[a];
}
};
/*
void build(vector<vector<int>>v){
for(auto i:v){
for(auto j:i)cout<<j<<" ";
cout<<'\n';
}
}
*/
vector<int>v[mxn+10];
int construct(vector<vector<int>>p){
int n=p.size();
dsu one,two;
vector<vector<int>>ans(n,vector<int>(n));
one.init();
two.init();
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(p[i][j]==1)one.merg(i,j);
if(p[i][j]!=p[j][i])return 0;
}
}
for(int i=0;i<n;i++)v[one.pa[i]].pb(i),one.pa[i]=one.find(i);
//case one
for(int i=0;i<n;i++)if(one.pa[i]!=i)ans[i][one.pa[i]]=1,ans[one.pa[i]][i]=1;
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(p[i][j]==2)two.merg(one.pa[i],one.pa[j]);//grouping
}
}
for(int i=0;i<n;i++)two.pa[i]=two.find(i);
fill(last,last+mxn,-1);
fill(first,first+mxn,-1);
//cyclic connection in group
for(int i=0;i<n;i++){
if(v[i].size())continue;
vector<int>check(n,-1);
for(int j=0;j<n;j++)check[j]=p[i][j];
for(int j=1;j<v[i].size();j++){
for(int k=0;k<n;k++)if(check[j]!=p[v[i][j]][k])return 0;
}
}
for(int i=0;i<n;i++){
if(one.pa[i]!=i)continue;
if(last[two.pa[i]]==-1)last[two.pa[i]]=i,first[two.pa[i]]=i;
else{
ans[last[two.pa[i]]][i]=1;
ans[i][last[two.pa[i]]]=1;
last[two.pa[i]]=i;
}
}
//finish the last connect
for(int i=0;i<n;i++){
if(last[i]==-1)continue;
if(first[i]==last[i])continue;
if(ans[first[i]][last[i]]){//already connected
if(v[first[i]].size()>1||v[last[i]].size()>1){
//connect to second node
if(v[last[i]].size()>1)swap(first[i],last[i]);
ans[first[i]][v[last[i]][1]]=1;
ans[v[last[i]][1]][first[i]]=1;
}
else return 0;
continue;
}
ans[first[i]][last[i]]=1;
ans[last[i]][first[i]]=1;
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(p[i][j]!=0)continue;
if((two.pa[i]==two.pa[j])||(one.pa[i]==one.pa[j]))return 0;
}
}
build(ans);
}
/*
int32_t main(){
fastio
int n;cin>>n;
vector<vector<int>>in(n,vector<int>(n));
for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>in[i][j];
construct(in);
return 0;
}*/