Submission #622731

#TimeUsernameProblemLanguageResultExecution timeMemory
622731Dremix10Sky Walking (IOI19_walk)C++17
10 / 100
4038 ms1048576 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; 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); int i,j; //int cnt[n+m] = {}; 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[] */ } } } priority_queue<ano> q; q.push({s,n+m,0}); vector<vector<ll> > d(n+m+1,vector<ll>(n+m+1,INF)); /* for(i=0;i<n;;i++){ d[i].assign(cnt[i],INF); } for(i=n;i<n+m;i++){ d[i].assign(1,INF); } */ d[s][n+m] = 0; 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.bef) p(temp.d) for(auto v : a[temp.x]){ ll cost; if(sky) cost = abs(x[temp.bef] - x[v]); else cost = abs(y[temp.bef-n] - y[v-n]); if(d[v][temp.x] > d[temp.x][temp.bef] + cost){ d[v][temp.x] = d[temp.x][temp.bef] + cost; q.push({v,temp.x,d[v][temp.x]}); } } } for(i=n;i<n+m;i++){ d[g][g] = min(d[g][g],d[g][i]+y[i-n]); } if(d[g][g] == INF)d[g][g] = -1; return d[g][g]; }
#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...