| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1083826 | rayan_bd | Connecting Supertrees (IOI20_supertrees) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
vector<int> par1(1001),sz1(1001,1),par2(1001),sz2(1001,1),par3(1001),sz3(1003,1);
int findPar1(int u){
if(par1[u]==u) return u;
return par1[u]=findPar1(par1[u]);
}
int findPar2(int u){
if(par2[u]==u) return u;
return par2[u]=findPar2(par2[u]);
}
int findPar3(int u){
if(par3[u]==u) return u;
return par3[u]=findPar3(par3[u]);
}
void unite1(int u,int v){
int ulp=findPar1(u);
int vlp=findPar1(v);
if(ulp==vlp) return;
if(sz1[ulp]>sz1[vlp]){
par1[vlp]=ulp;
sz1[ulp]+=sz1[vlp];
}else{
par1[ulp]=vlp;
sz1[vlp]+=sz1[ulp];
}
}
void unite2(int u,int v){
int ulp=findPar2(u);
int vlp=findPar2(v);
if(ulp==vlp) return;
if(sz2[ulp]>sz2[vlp]){
par2[vlp]=ulp;
sz2[ulp]+=sz2[vlp];
}else{
par2[ulp]=vlp;
sz2[vlp]+=sz2[ulp];
}
}
void unite3(int u,int v){
int ulp=findPar3(u);
int vlp=findPar3(v);
if(ulp==vlp) return;
if(sz3[ulp]>sz3[vlp]){
par3[vlp]=ulp;
sz3[ulp]+=sz3[vlp];
}else{
par3[ulp]=vlp;
sz3[vlp]+=sz3[ulp];
}
}
bool is_samee1(int u,int v){
return findPar1(u)==findPar1(v);
}
bool is_samee2(int u,int v){
return findPar2(u)==findPar2(v);
}
bool is_samee3(int u,int v){
return findPar3(u)==findPar3(v);
}
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> adj(n,vector<int>(n,0));
// subtask 4
for(int i=0;i<n;++i) par1[i]=par2[i]=par3[i]=i;
for(int i=0;i<n;++i){
for(int j=i+1;j<n;++j){
if(p[i][j]==2){
unite2(i,j);
unite3(i,j);
}
}
}
for(int i=0;i<n;++i){
for(int j=i+1;j<n;++j){
if(p[i][j]==1&&sz2[i]==1&&sz2[j]==1){
unite1(i,j);
unite3(i,j);
}
}
}
for(int i=0;i<n;++i){
if(sz2[findPar2(i)]==2) return 0;
for(int j=i+1;j<n;++j){
if(p[i][j]==0&&is_samee3(i,j)) return 0;
}
}
vector<int> last_2(n+1,-1),first(n+1,-1),last_1(n+1,-1);
for(int i=0;i<n;++i){
// connecting the 2 ways road
int ulp1=findPar2(i);
if(last_2[ulp1]!=-1&&sz2[ulp1]>2){
adj[i][last_2[ulp1]]=1;
adj[last_2[ulp1]][i]=1;
}
if(first[ulp1]==-1) first[ulp1]=i;
last_2[ulp1]=i;
ulp1=findPar1(i);
if(last_1[ulp1]!=-1&&sz1[ulp1]>1){
adj[i][last_1[ulp1]]=1;
adj[last_1[ulp1]][i]=1;
}
last_1[ulp1]=i;
}
for(int i=0;i<n;++i){
int ulp=findPar2(i);
if(sz2[ulp]>1) adj[last_2[ulp]][first[ulp]]=adj[first[ulp]][last_2[ulp]]=1;
}
for(int i=0;i<n;++i){
for(int j=i+1;j<n;++j){
if(p[i][j]==1&&!is_samee3(i,j)){
unite3(i,j);
adj[i][j]=adj[j][i]=1;
}
}
}
/*
for(int i=0;i<n;++i){
for(int j=i+1;j<n;++j){
if(adj[i][j]>0){
cout<<i<<" - "<<j<<'\n';
}
}
}*/
build(adj);
return 1;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("input.in","r",stdin);
freopen("output.out","w",stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n,q,u,v,w;cin>>n>>q;
vector<vector<int>> p(n,vector<int>(n,0));
for(int i=0;i<n;++i) p[i][i]=1;
while(q--){
cin>>u>>v>>w;
p[u][v]=p[v][u]=w;
}
construct(p);
//cout<<-1<<'\n';
return 0;
}