Submission #557262

#TimeUsernameProblemLanguageResultExecution timeMemory
557262hibikiRail (IOI14_rail)C++11
0 / 100
107 ms57916 KiB
#include "rail.h" #include<bits/stdc++.h> using namespace std; #define PB push_back #define F first #define S second int n; int dist[5050][5050]; int nw_c,nw_d,base_c,base_d; bool done[5050]; vector<int> l,r; vector<pair<int,int> > vec[5050]; int fi_dis(int a,int b) { if(a==b)return 0; if(dist[a][b])return dist[a][b]; return dist[a][b]=dist[b][a]=getDistance(a,b); } void findLocation(int N, int first, int location[], int stype[]) { // memset(dist,0,sizeof(dist)); // memset(done,0,sizeof(done)); // l.clear(); // r.clear(); // for(int i=0;i<5050;i++) // vec[i].clear(); n=N; nw_c=0; location[0]=first; stype[0]=1; done[0]=true; if(n==1)return ; for(int i=1;i<n;i++) vec[0].PB({fi_dis(0,i),i}); sort(vec[0].begin(),vec[0].end()); nw_d=vec[nw_c][0].S; location[nw_d]=location[nw_c]+vec[nw_c][0].F; stype[nw_d]=2; done[nw_d]=true; if(n==2)return ; for(int i=0;i<n;i++) { if(i==nw_d)continue; vec[nw_d].PB({fi_dis(nw_d,i),i}); } sort(vec[nw_d].begin(),vec[nw_d].end()); base_d=nw_d; base_c=vec[nw_d][0].S; nw_c=vec[nw_d][0].S; location[nw_c]=location[nw_d]-vec[nw_d][0].F; stype[nw_c]=1; done[nw_c]=true; for(int i=0;i<n;i++) { int a=base_c,b=i; if(a==b)continue; dist[a][b]=dist[b][a]=dist[0][i]-(location[a]-location[0]); vec[a].PB({dist[a][b],i}); } sort(vec[base_c].begin(),vec[base_c].end()); for(int i=0;i<vec[base_c].size();i++) { int go=vec[base_c][i].S; if(done[go])continue; if(dist[base_c][go]<dist[base_d][go]) r.PB(go); else l.PB(go); } nw_c=base_c; nw_d=base_d; for(int i=0;i<r.size();i++) { int go=r[i]; int nw_c_go=dist[base_c][go]-(location[nw_c]-location[base_c]); int nw_d_go=fi_dis(nw_d,go); done[go]=true; if(nw_c_go<nw_d_go) { // type d location[go]=location[nw_c]+nw_c_go; stype[go]=2; nw_d=go; } else { // type c location[go]=location[nw_d]-nw_d_go; stype[go]=1; if(location[nw_c]<location[go]) nw_c=go; } } nw_c=base_c; nw_d=base_d; for(int i=0;i<l.size();i++) { int go=l[i]; int nw_c_go=fi_dis(nw_c,go); int nw_d_go=dist[base_d][go]-(location[base_d]-location[nw_d]); done[go]=true; if(nw_d_go<nw_c_go) { // type c location[go]=location[nw_d]-nw_d_go; stype[go]=1; nw_c=go; } else { // type d location[go]=location[nw_c]+nw_c_go; stype[go]=2; if(location[go]<location[nw_d]) nw_d=go; } } return ; }

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:75:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i=0;i<vec[base_c].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~
rail.cpp:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i=0;i<r.size();i++)
      |                 ~^~~~~~~~~
rail.cpp:113:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for(int i=0;i<l.size();i++)
      |                 ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...