Submission #992356

#TimeUsernameProblemLanguageResultExecution timeMemory
992356MarwenElarbiSky Walking (IOI19_walk)C++17
10 / 100
651 ms325220 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long #define pb push_back const int nax=2e6; vector<pair<int,int>> adj[nax]; vector<long long> dis(nax); long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) { int n=x.size(); int k=l.size(); int cnt=n; vector<pair<int,pair<int,int>>> tab(k); for (int i = 0; i < k; ++i) { tab[i]={y[i],{l[i],r[i]}}; } sort(tab.begin(),tab.end()); map<int,pair<int,int>> mp; for (int i = 0; i < n; ++i) { mp[x[i]]={i,0}; } for (int i = 0; i < k; ++i) { for (int j = tab[i].se.fi; j <= tab[i].se.se; ++j) { if(tab[i].fi<=h[j]){ adj[cnt].pb({mp[x[j]].fi,tab[i].fi-mp[x[j]].se}); adj[mp[x[j]].fi].pb({cnt,tab[i].fi-mp[x[j]].se}); mp[x[j]]={cnt,tab[i].fi}; } if(j>tab[i].se.fi){ adj[cnt].pb({cnt-1,x[j]-x[j-1]}); adj[cnt-1].pb({cnt,x[j]-x[j-1]}); } cnt++; } } for (int i = 0; i < cnt; ++i) { dis[i]=1e18; } priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq; pq.push({0,s}); dis[s]=0; //cout <<"hey"<<endl; //int t=5; while(!pq.empty()){ //cout <<t<<endl; //if(t==0) break; //t--; ll d=pq.top().fi; ll x=pq.top().se; //cout <<x<<" "<<d<<endl; pq.pop(); if(x==g){ return d; } if(dis[x]!=d) continue; for(auto u:adj[x]){ //cout <<"n "<<u.fi<<endl; ll newd=u.se+d; //cout <<u.se<<endl; if(newd>=dis[u.fi]) continue; dis[u.fi]=newd; pq.push({newd,u.fi}); } } 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...