Submission #312418

#TimeUsernameProblemLanguageResultExecution timeMemory
312418huangqrConnecting Supertrees (IOI20_supertrees)C++14
56 / 100
266 ms22520 KiB
#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";*/ 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; else if(small[i]!=small[j]&&p[i][j]==1)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); } 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++; }*/ build(answer); return 1; }

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:128:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |   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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...