| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 927600 | MrDeboo | Connecting Supertrees (IOI20_supertrees) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
int dsu[1000];
vector<int>vct[1000][2];
vector<vector<int>>ans;
vector<vector<int>>p;
int fath(int in){
return dsu[in]=(dsu[in]==in?in:fath(dsu[in]));
}
int slv(vector<int>v){
for(auto &i:v){
for(auto &w:v){
if(!p[i][w])return 0;
}
}
vector<int>V;
vector<bool>vis(p.size());
for(int i=0;i<v.size();i++){
if(vis[i])continue;
int I=i;
for(int w=0;w<v.size();w++){
if(p[v[i]][v[w]]==1&&!vis[w]){
bool bl=1;
for(int j=0;j<v.size();j++){
if(v[j]==v[i]||v[j]==v[w])continue;
if(p[v[j]][v[i]]!=p[v[j]][v[w]])bl=0;
}
if(bl){
vis[w]=1;
ans[v[I]][v[w]]=1;
ans[v[w]][v[I]]=1;
I=w;
}
}
}
V.push_back(i);
vis[i]=1;
}
v=V;
for(int i=0;i<v.size();i++){
for(int w=i+1;w<v.size();w++){
if(p[v[i]][v[w]]!=2)return 0;
}
}
for(int i=0;i<v.size();i++){
ans[v[i]][v[(i+1)%v.size()]]=1;
ans[v[(i+1)%v.size()]][v[i]]=1;
}
return 1;
}
int construct(std::vector<std::vector<int>> P){
for(auto &i:P){
for(auto &w:i){
if(w>2)return 0;
}
}
for(auto &i:P)p.push_back(i);
int n=p.size();
for(int i=0;i<n;i++)dsu[i]=i;
for(int i=0;i<n;i++){
for(int w=0;w<n;w++){
if(i==w)continue;
vct[i][p[i][w]-1].push_back(w);
}
}
for(int i=0;i<n;i++){
vector<int>v(n);
ans.push_back(v);
}
vector<bool>vis(n);
for(int i=0;i<n;i++){
for(int w=0;w<n;w++){
if(vis[i]||vis[w]||i==w)continue;
if(p[i][w]){
deque<int>dq={i};
vector<int>vc;
while(dq.size()){
int a=dq.front();
vc.push_back(a);
dq.pop_front();
for(auto &j:vct[a][1]){
if(!vis[j]){
vis[j]=1;
dq.push_back(j);
}
}
for(auto &j:vct[a][0]){
if(!vis[j]){
vis[j]=1;
dq.push_back(j);
}
}
}
if(!slv(vc))return 0;
}
}
}
build(ans);
return 1;
}