Submission #622786

#TimeUsernameProblemLanguageResultExecution timeMemory
622786Dremix10Sky Walking (IOI19_walk)C++17
10 / 100
4066 ms707636 KiB
#include "walk.h" #include <bits/stdc++.h> 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; int cnt[n+m+1] = {}; for(i=0;i<n;i++){ for(j=0;j<m;j++){ if(l[j] <= i && i <= r[j] && h[i] >= y[j]){ a[i].push_back(n+j); a[n+j].push_back(i); cnt[i] ++; cnt[n+j] ++; } } } priority_queue<ano> q; vector<map<int,ll> > d(n+m+1,map<int,ll>()); cnt[s]++; cnt[n+m]++; a[s].push_back(n+m); a[n+m].push_back(s); q.push({s,n+m,0}); cnt[s] --; y.push_back(0); for(i=0;i<n+m;i++){ for(auto v : a[i]) d[i][v] = INF; } d[s][n+m] = 0; while(!q.empty()){ ano temp = q.top(); q.pop(); bool sky = false; if(temp.x >= n)sky = true; if(temp.d > d[temp.x][temp.who])continue; p2(temp.x,temp.who) p(temp.d) for(auto v : a[temp.x]){ //int v = a[temp.x][i]; if(v == temp.who)continue; ll cost; if(sky) cost = abs(x[temp.who] - x[v]); else cost = abs(y[temp.who-n] - y[v-n]); //int bef = -1; //for(j=0;j<cnt[v];j++) // if(a[v][j] == temp.x)bef = j; //assert(bef != -1); if(d[v][temp.x] > d[temp.x][temp.who] + cost){ d[v][temp.x] = d[temp.x][temp.who] + cost; q.push({v,temp.x,d[v][temp.x]}); } } } ll ans = INF; for(auto v : a[g]){ ans = min(ans,d[g][v]+y[v-n]); } if(ans == INF)ans = -1; return ans; }
#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...