| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 312425 | huangqr | 슈퍼트리 잇기 (IOI20_supertrees) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int construct(std::vector<std::vector<int>> p) {
int vis[1005];
std::vector<std::vector<int>> answer;
int n=p.size();
nnn=n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)if(p[i][j]==3||p[j][i]!=p[i][j])return 0;
}
int group[1005],small[1005],ctr=-1,ctr2=-1;;
vector<set<int> >groups,smalls;
unordered_map<int,vector<int> >groupstosmalls;
for(int i=0;i<n;i++)group[i]=small[i]=-1;
for(int i=0;i<n;i++){
if(p[i][i]!=1)return 0;
vector<int>r=p[i];
if(group[i]==-1){
group[i]=++ctr;
set<int>cgp={i};
for(int j=0;j<n;j++){
if(j==i)continue;
if(r[j]){
if(group[j]!=-1)return 0;
group[j]=ctr;
cgp.insert(j);
}
}
groups.push_back(cgp);
}
else{
int g=group[i];
for(int j=0;j<n;j++){
if(group[j]==g&&r[j]==0)return 0;
if(group[j]!=g&&r[j])return 0;
}
}
if(small[i]==-1){
small[i]=i;
groupstosmalls[group[i]].push_back(i);
set<int>cgp={i};
for(int j=0;j<n;j++){
if(j==i)continue;
if(r[j]==1){
if(small[j]!=-1)return 0;
small[j]=i;
cgp.insert(j);
}
}
smalls.push_back(cgp);
}
else{
int g=small[i];
for(int j=0;j<n;j++){
if(small[j]==g&&r[j]!=1)return 0;
if(small[j]!=g&&r[j]==1)return 0;
}
}
}
ctr++;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(group[i]!=group[j]&&p[i][j]!=0)return 0;
if(group[i]==group[j]&&p[i][j]==0)return 0;
if(small[i]==small[j]&&group[i]!=group[j])return 0;
if(small[i]==small[j]&&p[i][j]!=1)return 0;
if(small[i]!=small[j]&&group[i]==group[j]&&p[i][j]!=2)return 0;
}
}
//Set up the empty answer
for (int i = 0; i < n; i++) {
std::vector<int> row;
for(int j=0;j<n;j++)row.push_back(0);
answer.push_back(row);
}
//Creating lines from the sub-groups (smalls)
for(auto x:smalls){
auto y=++x.begin(),yy=x.begin();
while(y!=x.end()){
answer[*y][*yy]=answer[*yy][*y]=1;
y++,yy++;
}
}
for(auto x:groupstosmalls){
//Creating circles using 1 member of each sub-group
if(x.second.size()==1)continue; //No links formed
if(x.second.size()==2)return 0; //No loop is formed with only 2 members. This a crucial line.
for(int i=0;i<x.second.size()-1;i++){
answer[x.second[i]][x.second[i+1]]=answer[x.second[i+1]][x.second[i]]=1;
}
answer[x.second[0]][x.second[x.second.size()-1]]=answer[x.second[x.second.size()-1]][x.second[0]]=1;
}
build(answer);
return 1;
}
/* cout<<"Groups\n";
for(auto x:groups){
for(auto y:x){
cout<<y<<" ";
}
cout<<"\n";
}
cout<<"Smalls\n";
for(auto x:smalls){
for(auto y:x){
cout<<y<<" ";
}
cout<<"\n";
}
cout<<"g2s\n";
for(auto x:groupstosmalls){
cout<<x.first<<": ";
for(auto y:x.second)cout<<y<<" ";
cout<<"\n";
}
cout<<"small_val\n";
for(int i=0;i<n;i++)cout<<small[i]<<" ";
cout<<"\n";*/