# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
623167 | 2022-08-05T09:29:11 Z | Dremix10 | Sky Walking (IOI19_walk) | C++17 | 0 ms | 0 KB |
#include "walk.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; typedef long long ll; typedef pair<int,int> pi; typedef pair<ll,ll> pl; #define F first #define S second #define all(x) (x).begin(),(x).end() #ifdef dremix #define p(x) cerr<<#x<<" = "<<x<<endl; #define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl; #define pp(x) cerr<<#x<<" = "<<x.F<<"-"<<x.S<<endl; #define pv(x) cerr<<#x<<" = {";for(auto v : x)cerr<<v<<", ";cerr<<"}"<<endl; #define ppv(x) cerr<<#x<<" = {";for(auto v : x)cerr<<v.F<<"-"<<v.S<<", ";cerr<<"}"<<endl; #else #define p(x) {} #define p2(x,y) {} #define pp(x) {} #define pv(x) {} #define ppv(x) {} #endif const int N = 3e5+5; const int MOD = 1e9+7; const ll INF = 1e18+5; struct ano{ int x,who; ll d; bool operator<(const ano &x)const{ return d > x.d; } }; long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) { int n = x.size(); int m = l.size(); vector<vector<int> > a(n+m+1); int i,j; vector<vector<pi> > in(n),out(n); for(j=0;j<m;j++){ in[l[j]].push_back({y[j],n+j}); out[r[j]].push_back({y[j],n+j}); } set<pi> st; for(i=0;i<n;i++){ for(auto &x : in[i])st.insert(x); for(auto &x : st){ if(x.F > h[i])break; j = x.S; a[i].push_back(j); a[j].push_back(i); } for(auto &x : out[i])st.erase(x); } //if(n > 50)assert(0); priority_queue<ano> q; vector<__gnu_pbds::gp_hash_table<int,ll> > d(n+m+1,__gnu_pbds::gp_hash_table<int,ll>()); //vector<pl> dd(n+m,{INF); q.push({s,n+m,0}); int cnter=0; for(i=0;i<n+m;i++){ for(auto &v : a[i]){ d[i][v] = INF; cnter++; } } if(n>50) assert(cnter <= (m*10*2)); d[s][n+m] = 0; //dd[s] = {0,h[s]}; int cost,cover; bool sky; ll g,gg; while(!q.empty()){ ano temp = q.top(); q.pop(); sky = false; if(temp.x >= n)sky = true; gg = d[temp.x][temp.who]; if(temp.d > gg)continue; for(auto &v : a[temp.x]){ //if(v == temp.who)continue; if(sky) cost = abs(x[temp.who] - x[v]); else cost = abs(y[temp.who-n] - y[v-n]); g = d[v][temp.x]; d[temp.x][v] = min(d[temp.x][v], gg + cost); if(g > g + cost){ d[v][temp.x] = g + cost; q.push({v,temp.x,g+cost}); } } } ll ans = INF; for(auto v : a[g]){ ans = min(ans,d[g][v]+y[v-n]); } if(ans == INF)ans = -1; return ans; }