제출 #1036526

#제출 시각아이디문제언어결과실행 시간메모리
1036526AbitoSky Walking (IOI19_walk)C++17
10 / 100
4137 ms710020 KiB
#include "walk.h" #include <bits/stdc++.h> #define pb push_back #define F first #define S second #define int long long #define ep insert using namespace std; const int N=1e5+5; int n,m,a[N],b[N],L[N],R[N],c[N]; set<pair<int,int>> s[2][N]; map<pair<int,int>,int> dis,vis; vector<pair<int,int>> ad[N],er[N]; void dijkstra(int src){ dis[{src,0}]=0; priority_queue<vector<int>> pq; pq.push({0,src,0}); while (!pq.empty()){ int x=pq.top()[1],y=pq.top()[2]; pq.pop(); if (vis[{x,y}]) continue; //cout<<x<<' '<<y<<endl; vis[{x,y}]=1; if (y==0){ if (!s[0][x].empty()){ int to=(*s[0][x].begin()).S; if (dis.find({x,to})==dis.end() || dis[{x,to}]>dis[{x,y}]+c[to]){ dis[{x,to}]=dis[{x,y}]+c[to]; pq.push({-dis[{x,to}],x,to}); } } if (dis.find({x,m+1})==dis.end() || dis[{x,m+1}]>dis[{x,y}]+b[x]){ dis[{x,m+1}]=dis[{x,y}]+b[x]; pq.push({-dis[{x,m+1}],x,m+1}); } continue; } if (y==m+1){ if (!s[0][x].empty()){ int to=(*--s[0][x].end()).S; if (dis.find({x,to})==dis.end() || dis[{x,to}]>dis[{x,y}]+b[x]-c[to]){ dis[{x,to}]=dis[{x,y}]+b[x]-c[to]; pq.push({-dis[{x,to}],x,to}); } } if (dis.find({x,0})==dis.end() || dis[{x,0}]>dis[{x,y}]+b[x]){ dis[{x,0}]=dis[{x,y}]+b[x]; }continue; } if (dis.find({x,0})==dis.end() || dis[{x,0}]>dis[{x,y}]+c[y]){ dis[{x,0}]=dis[{x,y}]+c[y]; pq.push({-dis[{x,0}],x,0}); } if (dis.find({x,m+1})==dis.end() || dis[{x,m+1}]>dis[{x,y}]+b[x]-c[y]){ dis[{x,m+1}]=dis[{x,y}]+b[x]-c[y]; pq.push({-dis[{x,m+1}],x,m+1}); } auto it=s[0][x].upper_bound({c[y],y}); if (it!=s[0][x].end()){ int to=(*it).S; if (dis.find({x,to})==dis.end() || dis[{x,to}]>dis[{x,y}]+abs(c[to]-c[y])){ dis[{x,to}]=dis[{x,y}]+abs(c[to]-c[y]); pq.push({-dis[{x,to}],x,to}); } } it=s[0][x].lower_bound({c[y],y}); if (it!=s[0][x].begin()){ int to=(*--it).S; if (dis.find({x,to})==dis.end() || dis[{x,to}]>dis[{x,y}]+abs(c[to]-c[y])){ dis[{x,to}]=dis[{x,y}]+abs(c[to]-c[y]); pq.push({-dis[{x,to}],x,to}); } } it=s[1][y].upper_bound({a[x],x}); if (it!=s[1][y].end()){ int to=(*it).S; if (dis.find({to,y})==dis.end() || dis[{to,y}]>dis[{x,y}]+abs(a[to]-a[x])){ dis[{to,y}]=dis[{x,y}]+abs(a[to]-a[x]); pq.push({-dis[{to,y}],to,y}); } } it=s[1][y].lower_bound({a[x],x}); if (it!=s[1][y].begin()){ int to=(*--it).S; if (dis.find({to,y})==dis.end() || dis[{to,y}]>dis[{x,y}]+abs(a[to]-a[x])){ dis[{to,y}]=dis[{x,y}]+abs(a[to]-a[x]); pq.push({-dis[{to,y}],to,y}); } } }return; } long long min_distance(vector<int32_t> x, vector<int32_t> h, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int32_t S, int32_t g) { n=x.size(),m=l.size(); for (int i=0;i<n;i++) a[i+1]=x[i],b[i+1]=h[i]; for (int j=0;j<m;j++) L[j+1]=l[j]+1,R[j+1]=r[j]+1,c[j+1]=y[j]; for (int j=1;j<=m;j++){ ad[L[j]].pb({c[j],j}); er[R[j]].pb({c[j],j}); } set<pair<int,int>> ms; for (int i=1;i<=n;i++){ for (auto u:ad[i]) ms.ep(u); for (auto u:ms){ if (u.F<=b[i]) s[0][i].ep(u),s[1][u.S].ep({a[i],i}); else break; } for (auto u:er[i]) ms.erase(u); } dijkstra(S+1); if (dis.find({g+1,0})==dis.end()) return -1; return dis[{g+1,0}]; }
#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...