Submission #622776

#TimeUsernameProblemLanguageResultExecution timeMemory
622776Dremix10Sky Walking (IOI19_walk)C++17
10 / 100
4075 ms156056 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,bef,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<vector<ll> > d(n+m+1,vector<ll>()); cnt[s]++; cnt[n+m]++; a[s].push_back(n+m); a[n+m].push_back(s); for(i=0;i<=n+m;i++){ d[i].assign(cnt[i],INF); } d[s][cnt[s]-1] = 0; q.push({s,cnt[s]-1,n+m,0}); cnt[s] --; y.push_back(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.bef])continue; p2(temp.x,temp.who) p(temp.d) for(i=0;i<cnt[temp.x];i++){ 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][bef] > d[temp.x][temp.bef] + cost){ d[v][bef] = d[temp.x][temp.bef] + cost; q.push({v,bef,temp.x,d[v][bef]}); } } } ll ans = INF; for(i=0;i<cnt[g];i++){ ans = min(ans,d[g][i]+y[a[g][i]-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...