Submission #579062

#TimeUsernameProblemLanguageResultExecution timeMemory
579062ogibogi2004Highway Tolls (IOI18_highway)C++14
100 / 100
264 ms12328 KiB
#include "highway.h" #include<bits/stdc++.h> using namespace std; const int MAXN=9e4+6; const int MAXM=(1<<17); vector<pair<int,int> >g[MAXN]; int distu[MAXN],distv[MAXN]; int parEdgeU[MAXN]; int parEdgeV[MAXN]; void find_pair(int N, vector<int> U, vector<int> V, int A, int B) { int M = U.size(); for(int i=0;i<M;i++) { g[U[i]].push_back({V[i],i}); g[V[i]].push_back({U[i],i}); } vector<int>w; w=vector<int>(M,0); long long dist=(long long)ask(w); long long low=0,high=M-1,best; while(low<=high) { int mid=(low+high)/2; for(int j=0;j<w.size();j++)w[j]=0; for(int j=0;j<=mid;j++) { w[j]=1; } if(ask(w)==dist) { low=mid+1; } else { best=mid; high=mid-1; } } int u=U[best],v=V[best]; queue<int>bfsu,bfsv; bfsu.push(u); bfsv.push(v); memset(distu,-1,sizeof(distu)); memset(distv,-1,sizeof(distv)); distu[u]=0; parEdgeU[u]=-1; distv[v]=0; parEdgeV[v]=-1; vector<pair<int,int> >tv,tu; while(!bfsu.empty()) { int t=bfsu.front(); bfsu.pop(); for(auto xd:g[t]) { if(distu[xd.first]==-1) { distu[xd.first]=distu[t]+1; parEdgeU[xd.first]=xd.second; bfsu.push(xd.first); } } } while(!bfsv.empty()) { int t=bfsv.front(); bfsv.pop(); for(auto xd:g[t]) { if(distv[xd.first]==-1) { distv[xd.first]=distv[t]+1; parEdgeV[xd.first]=xd.second; bfsv.push(xd.first); } } } for(int i=0;i<N;i++) { if(distu[i]<distv[i]) { tu.push_back({distu[i],i}); } else { tv.push_back({distv[i],i}); } } sort(tu.begin(),tu.end()); sort(tv.begin(),tv.end()); low=0,high=tu.size()-1; int s,t; while(low<=high) { int mid=(low+high)/2; for(int j=0;j<w.size();j++)w[j]=0; w[best]=1; for(int j=1;j<=mid;j++) { w[parEdgeU[tu[j].second]]=1; } for(int j=1;j<tv.size();j++) { w[parEdgeV[tv[j].second]]=1; } for(int j=0;j<w.size();j++)w[j]=1-w[j]; /*for(int j=0;j<w.size();j++)cout<<w[j]<<" "; cout<<endl; cout<<low<<" "<<high<<" "<<mid<<" "<<ask(w)<<endl;*/ if(ask(w)>(long long)dist) { low=mid+1; } else { s=tu[mid].second; high=mid-1; } } low=0;high=tv.size()-1; //cout<<"dist: "<<dist<<" "<<dist*1ll/A*1ll*B<<endl; while(low<=high) { int mid=(low+high)/2; for(int j=0;j<w.size();j++)w[j]=0; w[best]=1; for(int j=1;j<=mid;j++) { w[parEdgeV[tv[j].second]]=1; } for(int j=1;j<tu.size();j++) { w[parEdgeU[tu[j].second]]=1; } for(int j=0;j<w.size();j++)w[j]=1-w[j]; /*for(int j=0;j<w.size();j++)cout<<w[j]<<" "; cout<<endl; cout<<low<<" "<<high<<" "<<mid<<" "<<ask(w)<<endl;*/ if(ask(w)>(long long)dist) { low=mid+1; } else { t=tv[mid].second; high=mid-1; } } /*cout<<"tu:\n"; for(auto xd:tu)cout<<xd.second<<" "; cout<<endl; cout<<"tv:\n"; for(auto xd:tv)cout<<xd.second<<" "; cout<<endl; cout<<s<<" "<<t<<endl; cout<<s<<" "<<t<<endl;*/ answer(s,t); }

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for(int j=0;j<w.size();j++)w[j]=0;
      |                     ~^~~~~~~~~
highway.cpp:96:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         for(int j=0;j<w.size();j++)w[j]=0;
      |                     ~^~~~~~~~~
highway.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for(int j=1;j<tv.size();j++)
      |                     ~^~~~~~~~~~
highway.cpp:106:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for(int j=0;j<w.size();j++)w[j]=1-w[j];
      |                     ~^~~~~~~~~
highway.cpp:125:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         for(int j=0;j<w.size();j++)w[j]=0;
      |                     ~^~~~~~~~~
highway.cpp:131:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         for(int j=1;j<tu.size();j++)
      |                     ~^~~~~~~~~~
highway.cpp:135:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |         for(int j=0;j<w.size();j++)w[j]=1-w[j];
      |                     ~^~~~~~~~~
highway.cpp:158:11: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
  158 |     answer(s,t);
      |     ~~~~~~^~~~~
highway.cpp:158:11: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
highway.cpp:39:17: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |     int u=U[best],v=V[best];
      |                 ^
#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...