Submission #762363

#TimeUsernameProblemLanguageResultExecution timeMemory
762363aihaySky Walking (IOI19_walk)C++14
0 / 100
2325 ms197528 KiB
#include <bits/stdc++.h> using namespace std; typedef long long LL; #define F first #define S second #define PB push_back #define FR(i,a,b) for(int i=(a);i<(b);i++) #define FOR(i,n) FR(i,0,n) #define SZ(x) int(x.size()) const LL MAAX=1e18; const int MOD=1e9+7; const int MAX=1e9; int n,m,s,g,x[100010],h[100010],l[100010],r[100010],y[100010],idxx,tim; pair<int,int> srtb[100010]; pair<int,pair<int,int>> srts[100010]; LL cst[1000010]; vector<int> v[2000010]; map<pair<int,int>,int> mp; pair<int,int> inter[2000010]; LL dijk(){ for(int i=0;i<idxx;i++) cst[i]=MAAX; priority_queue<pair<LL,int>> pq; pq.push({0,1}); while(pq.size()){ LL cost=-pq.top().F; int idx=pq.top().S; pq.pop(); if(cost>cst[idx]) continue; cst[idx]=cost; if(idx==2) break; for(int i=0;i<v[idx].size();i++){ int x1=inter[idx].F,x2=inter[v[idx][i]].F; int y1=inter[idx].S,y2=inter[v[idx][i]].S; LL ncst=cost+abs(x2-x1)+abs(y2-y1); int nidx=v[idx][i]; if(ncst<cst[nidx]){ cst[nidx]=ncst; pq.push({-ncst,nidx}); } } } if(cst[2]==MAAX) cst[2]=-1; return cst[2]; } map<int,vector<int>> vec; LL min_distance(vector<int> X,vector<int> H,vector<int> L,vector<int> R,vector<int> Y,int S,int G){ tim=clock(); n=X.size(); m=L.size(); s=S,g=G; for(int i=0;i<n;i++){ x[i]=X[i]; h[i]=H[i]; vec[x[i]].PB(0); srtb[i]={-h[i],x[i]}; } sort(srtb,srtb+n); idxx++; mp[{x[s],0}]=idxx++; inter[1]={x[s],0}; mp[{x[g],0}]=idxx++; inter[2]={x[g],0}; for(int i=0;i<n;i++){ srtb[i].F*=-1; if(mp[{x[i],0}]==0){ mp[{x[i],0}]=idxx++; inter[idxx-1]={x[i],0}; } } for(int i=0;i<m;i++){ l[i]=L[i]; r[i]=R[i]; y[i]=Y[i]; srts[i]={-y[i],{x[l[i]],x[r[i]]}}; } sort(srts,srts+m); set<int> curst; int idx=0; for(int i=0;i<m;i++){ if(srts[i].F==1) break; srts[i].F=-srts[i].F; while(idx<n&&srtb[idx].F>=srts[i].F) curst.insert(srtb[idx++].S); int lst=-1; for(set<int>::iterator j=curst.lower_bound(srts[i].S.F);j!=curst.end()&&(*j)<=srts[i].S.S;j++){ int xx=0; if(xx==0){ mp[{(*j),srts[i].F}]=xx=idxx++; inter[idxx-1]={(*j),srts[i].F}; vec[(*j)].PB(srts[i].F); } if(~lst){ v[lst].PB(xx); v[xx].PB(lst); } lst=xx; } } for(int i=0;i<n;i++){ sort(vec[x[i]].begin(),vec[x[i]].end()); for(int j=1;j<vec[x[i]].size();j++){ v[mp[{x[i],vec[x[i]][j]}]].PB(mp[{x[i],vec[x[i]][j-1]}]); v[mp[{x[i],vec[x[i]][j-1]}]].PB(mp[{x[i],vec[x[i]][j]}]); } } return dijk(); }

Compilation message (stderr)

walk.cpp: In function 'LL dijk()':
walk.cpp:35:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int i=0;i<v[idx].size();i++){
      |               ~^~~~~~~~~~~~~~
walk.cpp: In function 'LL min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:107:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |   for(int j=1;j<vec[x[i]].size();j++){
      |               ~^~~~~~~~~~~~~~~~~
#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...