이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int vis[1005];
std::vector<std::vector<int>> answer;
int nnn;
void dfs(int pos,vector<int>vd){
vd.push_back(pos);
vis[pos]++;
for(int i=0;i<nnn;i++){
if(answer[pos][i]==1){
for(auto x:vd)if(x==i)goto br;
dfs(i,vd);
}
br:;
}
}
int construct(std::vector<std::vector<int>> p) {
using namespace std;
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++;
/* 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";*/
//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);
}
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){
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;
}
if(x.second.size()-1)answer[x.second[0]][x.second[x.second.size()-1]]=answer[x.second[x.second.size()-1]][x.second[0]]=1;
}
/* auto y=++groups.begin(),yy=groups.begin();
auto aa=yy->begin(),bb=groups.back().begin();
answer[*aa][*bb]=answer[*bb][*aa]=1;
while(y!=groups.end()){
auto aa=yy->begin(),bb=y->begin();
answer[*aa][*bb]=answer[*bb][*aa]=1;
y++,yy++;
}*/
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)vis[j]=0;
dfs(i,vector<int>());
for(int j=0;j<n;j++)if(vis[j]!=p[i][j])return 0;
}
build(answer);
return 1;
}
컴파일 시 표준 에러 (stderr) 메시지
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:121:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(int i=0;i<x.second.size()-1;i++){
| ~^~~~~~~~~~~~~~~~~~
supertrees.cpp:31:37: warning: unused variable 'ctr2' [-Wunused-variable]
31 | int group[1005],small[1005],ctr=-1,ctr2=-1;;
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |