Submission #71302

#TimeUsernameProblemLanguageResultExecution timeMemory
71302KmcodeSimurgh (IOI17_simurgh)C++14
51 / 100
180 ms20456 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*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=MAX-3; const int black=MAX-2; 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); } vector<int> mer[MAX]; 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<v.size();i++){ mer[uf.root(i)].push_back(i); } for(int i=0;i<v.size();i++){ if(i==white||i==black)continue; //mergeable if(mer[i].size()==0)continue; UF uf3; bool ok=false; for(int el:mer[i]){ int a=v[el].first; int b=v[el].second; if(uf3.root(a)==uf3.root(b)){ ok=true; break; } uf3.merge(a,b); if(uf2.root(a)==uf2.root(b)){ ok=true; break; } } if(ok==false){ for(int el:mer[i]){ road.push_back(el); int a=v[el].first; int b=v[el].second; //uf2.merge(a,b); } } } assert(ans.size()>=n-1); return ans; } } std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) { return solver::find_roads(n,u,v); }

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:104:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<u1.size();i++){
               ~^~~~~~~~~~
simurgh.cpp:112:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<road.size();i++){
                ~^~~~~~~~~~~~
simurgh.cpp:117:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v.size();i++){
               ~^~~~~~~~~
simurgh.cpp:135:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v.size();i++){
               ~^~~~~~~~~
simurgh.cpp:141:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v.size();i++){
               ~^~~~~~~~~
simurgh.cpp:144:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v.size();i++){
               ~^~~~~~~~~
simurgh.cpp:166:10: warning: unused variable 'a' [-Wunused-variable]
      int a=v[el].first;
          ^
simurgh.cpp:167:10: warning: unused variable 'b' [-Wunused-variable]
      int b=v[el].second;
          ^
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from simurgh.cpp:1:
simurgh.cpp:172:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(ans.size()>=n-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...