| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1347122 | Rawlat_vanak | 슈퍼트리 잇기 (IOI20_supertrees) | C++20 | 0 ms | 0 KiB |
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define speedIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define f first
#define s second
#define pii pair<int,int>
#define pb push_back
struct DSU{
vector<int> parent,sz;
vector<vector<int>> elements;
DSU(int n){
parent.clear();
parent.resize(n);
iota(parent.begin(),parent.end(),0);
sz.clear();
sz.resize(n,1);
elements.clear();
elements.resize(n);
for(int i=0;i<n;i++){
elements[i].pb(i);
}
}
int find(int u){
if(u==parent[u]){
return u;
}
return parent[u]=find(parent[u]);
}
void unite(int u, int v){
int x=find(u),y=find(v);
if(x==y){
return;
}
if(sz[x]<sz[y]){
swap(u,v);
swap(x,y);
}
parent[y]=x;
sz[x]+=sz[y];
for(int i:elements[y]){
elements[x].pb(i);
}
}
};
int construct(vector<vector<int>> p){
int n=p.size();
int flag=1;
vector<vector<int>> adj(n,vector<int>(n,0)),b(n,vector<int>(n,0));
for(int i=0;i<n;i++){
adj[i][i]=1;
}
DSU dsuall(n),dsuone(n);
//vector<bool> visited(n,false);
//vector<int> thetwo;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(p[i][j]==3){
flag=0;
}else if(p[i][j]==2){
//dsutwo.unite(i,j);
dsuall.unite(i,j);
/*if(!visited[i]){
thetwo.pb(i);
visited[i]=true;
}
if(!visited[j]){
thetwo.pb(j);
visited[j]=true;
}*/
}else if(p[i][j]==1){
dsuall.unite(i,j);
if(dsuone.find(i)!=dsuone.find(j)){
dsuone.unite(i,j);
b[i][j]=1;
b[j][i]=1;
}
//dsuone.unite(i,j);
}
}
}
vector<int> reps;
for(int i=0;i<n;i++){
if(i==dsuall.parent[i]){
reps.pb(i);
}
}
for(int i:reps){
vector<int> thetwos;
for(int j:dsuall.elements[i]){
if(j==dsuone.parent[j]){
thetwos.pb(j);
}
for(int k:dsuall.elements[i]){
adj[j][k]=1;
}
}
/*for(int j:thetwos){
cout<<j<<' ';
}
cout<<"weofhowefoew\n";*/
for(int j=0;j<thetwos.size();j++){
for(int k=j+1;k<thetwos.size();k++){
for(int x:dsuone.elements[thetwos[j]]){
for(int y:dsuone.elements[thetwos[k]]){
//cout<<x<<' '<<y<<"BALEBALE\n";
adj[x][y]=2;
adj[y][x]=2;
}
}
}
}
if(thetwos.size()>=2){
for(int i=0;i<thetwos.size();i++){
int u=thetwos[i];
int v=thetwos[(i+1)%thetwos.size()];
b[u][v]=1;
b[v][u]=1;
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(adj[i][j]!=p[i][j]){
flag=0;
}
}
}
if(flag){
build(b);
}
return flag;
}