Submission #1058297

#TimeUsernameProblemLanguageResultExecution timeMemory
1058297UnforgettableplSky Walking (IOI19_walk)C++17
10 / 100
4097 ms1048576 KiB
#include "walk.h" #include <bits/stdc++.h> using namespace std; 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<pair<int,int>>> points(n); vector<vector<pair<int,int>>> adj(n); int S = n; for(int i=0;i<n;i++)points[i].emplace_back(i,0); vector<tuple<int,int,int>> skywalks; for(int i=0;i<m;i++)skywalks.emplace_back(y[i],l[i],r[i]); sort(skywalks.begin(), skywalks.end()); auto add_point = [&](int x,int h) { adj.emplace_back(); adj[S].emplace_back(points[x].back().first,h-points[x].back().second); adj[points[x].back().first].emplace_back(S,h-points[x].back().second); points[x].emplace_back(S,h); return S++; }; for(int i=0;i<m;i++){ auto [height,left,right] = skywalks[i]; auto last_point = add_point(left,height); auto last_x = x[left]; for(int j=left+1;j<=right;j++) { if(h[j]<height)continue; auto curr_point = add_point(j,height); adj[curr_point].emplace_back(last_point,x[j]-last_x); adj[last_point].emplace_back(curr_point,x[j]-last_x); last_point=curr_point; last_x=x[j]; } } priority_queue<pair<long long,int>> q; vector<bool> visited(S); q.emplace(0,s); while(!q.empty()) { auto [dist,idx] = q.top();q.pop();dist=-dist; if(visited[idx])continue; visited[idx]=true; if(idx==g)return dist; for(auto&[v,c]:adj[idx])if(!visited[v])q.emplace(-dist-c,v); } return -1; }
#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...