Submission #71293

#TimeUsernameProblemLanguageResultExecution timeMemory
71293KmcodeSimurgh (IOI17_simurgh)C++14
Compilation error
0 ms0 KiB
#include<bits/stdc++.h> //#include "books.h" using namespace std; //#include "simurgh.h" int count_common_roads(const std::vector<int>& r); #define MAX 512 struct UF{ int belong[MAX]; int sz[MAX]; int col[MAX]; UF(){ memset(belong,-1,sizeof(belong)); for(int i=0;i<MAX;i++)sz[i]=1; } inline int root(int b){ if(belong[b]==-1){ return b; } return belong[b]=root(belong[b]); } void merge(int a,int b){ a=root(a); b=root(b); if(a==b)return; if(a>b)swap(a,b); belong[a]=b; sz[b]+=sz[a]; } }; namespace solver{ const int white=503; const int black=504; vector<pair<int,int> > v; vector<pair<int,int> > g[MAX]; int id[MAX]; int pr[MAX]; int dep[MAX]; UF uf; vector<int> road; vector<int> swa; inline void dfs(int b,int pr2=-1,int d=0){ dep[b]=d; for(auto go:g[b]){ if(go.first==pr2)continue; dfs(go.first,b,d+1); pr[go.first]=b; id[go.first]=go.second; } } int ini; int cn; int ask(){ cn++; assert(cn<=30000); return count_common_roads(road); } void make_tree(){ UF uf2; for(int i=0;i<v.size();i++){ swa.push_back(-1); if(uf2.root(v[i].first)!=uf2.root(v[i].second)){ uf2.merge(v[i].first,v[i].second); g[v[i].first].push_back(make_pair(v[i].second,i) ); g[v[i].second].push_back(make_pair(v[i].first,i) ); road.push_back(i); swa[i]=road.size()-1; } } ini=ask(); } int query(int exp,int add){ road[swa[exp]]=add; int z=ask(); road[swa[exp]]=exp; return z-ini; } inline void check(int tree1,int tree2){ int r1=uf.root(tree1); int r2=uf.root(tree2); if(r1==r2)return; if(r1==black||r1==white){ if(r2==black||r2==white){ return; } } int ret=query(tree1,tree2); if(ret==0){ uf.merge(tree1,tree2); return; } if(ret>0){ uf.merge(black,tree2); uf.merge(white,tree1); return; } uf.merge(black,tree1); uf.merge(white,tree2); } std::vector<int> find_roads(int n, std::vector<int> u1, std::vector<int> v1) { for(int i=0;i<u1.size();i++){ v.push_back(make_pair(u1[i],v1[i])); } make_tree(); if(ini==n-1){ return road; } if(ini==0){ for(int i=0;i<road.size();i++){ uf.merge(road[i],white); } } dfs(0); for(int i=0;i<v.size();i++){ if(dep[v[i].first]>dep[v[i].second])swap(v[i].first,v[i].second); if(pr[v[i].second]==v[i].first)continue; int a=v[i].first; int b=v[i].second; while(a!=b){ if(dep[a]<dep[b]){ check(id[b],i); b=pr[b]; } else{ check(id[a],i); a=pr[a]; } } } vector<int> ans; UF uf2; for(int i=0;i<v.size();i++){ if(uf.root(i)==black){ ans.push_back(i); uf2.merge(v[i].first,v[i].second); } } for(int i=0;i<road.size();i++){ int a=v[road[i]].first; int b=v[road[i]].second; if(uf2.root(a)!=uf2.root(b)){ uf2.merge(a,b); ans.push_back(road[i]); } } return ans; } }

Compilation message (stderr)

simurgh.cpp: In function 'void solver::make_tree()':
simurgh.cpp:62:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v.size();i++){
               ~^~~~~~~~~
simurgh.cpp: In function 'std::vector<int> solver::find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:103:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<u1.size();i++){
               ~^~~~~~~~~~
simurgh.cpp:111:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<road.size();i++){
                ~^~~~~~~~~~~~
simurgh.cpp:116:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v.size();i++){
               ~^~~~~~~~~
simurgh.cpp:134:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v.size();i++){
               ~^~~~~~~~~
simurgh.cpp:140:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<road.size();i++){
               ~^~~~~~~~~~~~
/tmp/ccthaXOn.o: In function `main':
grader.cpp:(.text.startup+0x31f): undefined reference to `find_roads(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status