| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1111088 | epicci23 | Sky Walking (IOI19_walk) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
#include "walk.h"
#define ll long long
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (ll)a.size()
using namespace std;
const ll INF = 1e18;
vector<vector<array<ll,2>>> v;
vector<array<ll,2>> nodes;
inline ll get_ind(ll x,ll y){
ll it = lower_bound(all(nodes),array<ll,2>{x,y})-nodes.begin();
return it;
}
ll dijkstra(ll _s,ll _t){
vector<ll> dist(sz(v)+5,INF);
dist[_s]=0;
priority_queue<array<ll,2>> pq;
pq.push({{0,_s}});
while(!pq.empty()){
ll c = pq.top()[1];
ll d = -pq.top()[0];
pq.pop();
if(d>dist[c]) continue;
for(array<ll,2> u:v[c]){
if(u[1]+d<dist[u[0]]){
dist[u[0]]=d+u[1];
pq.push({-dist[u[0]],u[0]});
}
}
}
return dist[_t];
}
long long min_distance(vector<int> X,vector<int> H, vector<int> L,vector<int> R,vector<int> Y, int _st, int _tt){
ll n = sz(x),m = sz(l);
ll ar[n+5],he[n+5],l[m+5],r[m+5],y[m+5];
for(ll i=1;i<=n;i++) ar[i] = X[i-1];
for(ll i=1;i<=n;i++) he[i] = H[i-1];
for(ll i=1;i<=n;i++){
nodes.push_back({ar[i],0});
nodes.push_back({ar[i],he[i]});
}
for(ll i=1;i<=m;i++) l[i]=L[i-1];
for(ll i=1;i<=m;i++) r[i]=R[i-1];
for(ll i=1;i<=m;i++) y[i]=Y[i-1];
vector<array<ll,3>> sky;
for(ll i=1;i<=m;i++) sky.push_back({y[i],l[i],r[i]});
sort(all(sky));
multiset<ll> xs;
for(ll i=1;i<=n;i++) xs.insert(ar[i]);
vector<ll> lol;
for(ll i=1;i<=n;i++) lol.push_back(i);
sort(all(lol),[&](ll a,ll b){
return he[a] < he[b];
});
ll _p=0;
for(auto x:sky){
nodes.push_back({ar[x[1]],x[0]});
nodes.push_back({ar[x[2]],x[0]});
while(_p<n && he[lol[_p]]<x[0]) xs.erase(xs.find(ar[lol[_p++]]));
auto it = xs.lower_bound(ar[x[1]]);
while(it!=xs.end() && (*it)<=ar[x[2]]){
nodes.push_back({(*it),x[0]});
it++;
}
}
sort(all(nodes));
nodes.erase(unique(all(nodes)),nodes.end());
v.resize(sz(nodes)+5);
map<ll,vector<ll>> mp;
for(auto x:nodes) mp[x[0]].push_back(x[1]);
for(auto x:mp) sort(all(mp[x.first]));
for(ll i=1;i<=n;i++){
v[get_ind(ar[i],0)].push_back({get_ind(ar[i],he[i]),he[i]});
v[get_ind(ar[i],he[i])].push_back({get_ind(ar[i],0),he[i]});
for(ll j=1;j<sz(mp[ar[i]]);j++){
if(mp[ar[i]][j]>he[i]) break;
ll _a = get_ind(ar[i],mp[ar[i]][j]);
ll _b = get_ind(ar[i],mp[ar[i]][j-1]);
ll _c = mp[ar[i]][j] - mp[ar[i]][j-1];
v[_a].push_back({_b,_c});
v[_b].push_back({_a,_c});
}
}
_p=0;
xs.clear();
for(ll i=1;i<=n;i++) xs.insert(ar[i]);
for(auto x:sky){
vector<array<ll,2>> curi;
curi.push_back({ar[x[1]],x[0]});
curi.push_back({ar[x[2]],x[0]});
while(_p<n && he[lol[_p]]<x[0]) xs.erase(xs.find(ar[lol[_p++]]));
auto it = xs.lower_bound(ar[x[1]]);
while(it!=xs.end() && (*it)<=ar[x[2]]){
curi.push_back({(*it),x[0]});
it++;
}
sort(all(curi));
curi.erase(unique(all(curi)),curi.end());
for(ll j=1;j<sz(curi);j++){
ll _a = get_ind(curi[j][0],curi[j][1]);
ll _b = get_ind(curi[j-1][0],curi[j-1][1]);
ll _c = curi[j][0] - curi[j-1][0];
v[_a].push_back({_b,_c});
v[_b].push_back({_a,_c});
}
}
ll ans = dijkstra(get_ind(ar[_st],0),get_ind(ar[_tt],0));
if(ans==INF) return -1;
return ans;
}
/*void _(){
ll n,m,_st,_tt;
cin >> n >> m >> _st >> _tt;
ll ar[n+5],he[n+5],l[m+5],r[m+5],y[m+5];
for(ll i=1;i<=n;i++) cin >> ar[i];
for(ll i=1;i<=n;i++) cin >> he[i];
for(ll i=1;i<=n;i++){
nodes.push_back({ar[i],0});
nodes.push_back({ar[i],he[i]});
}
for(ll i=1;i<=m;i++) cin >> l[i];
for(ll i=1;i<=m;i++) cin >> r[i];
for(ll i=1;i<=m;i++) cin >> y[i];
vector<array<ll,3>> sky;
for(ll i=1;i<=m;i++) sky.push_back({y[i],l[i],r[i]});
sort(all(sky));
multiset<ll> xs;
for(ll i=1;i<=n;i++) xs.insert(ar[i]);
vector<ll> lol;
for(ll i=1;i<=n;i++) lol.push_back(i);
sort(all(lol),[&](ll a,ll b){
return he[a] < he[b];
});
ll _p=0;
for(auto x:sky){
nodes.push_back({ar[x[1]],x[0]});
nodes.push_back({ar[x[2]],x[0]});
while(_p<n && he[lol[_p]]<x[0]) xs.erase(xs.find(ar[lol[_p++]]));
auto it = xs.lower_bound(ar[x[1]]);
while(it!=xs.end() && (*it)<=ar[x[2]]){
nodes.push_back({(*it),x[0]});
it++;
}
}
sort(all(nodes));
nodes.erase(unique(all(nodes)),nodes.end());
v.resize(sz(nodes)+5);
map<ll,vector<ll>> mp;
for(auto x:nodes) mp[x[0]].push_back(x[1]);
for(auto x:mp) sort(all(mp[x.first]));
for(ll i=1;i<=n;i++){
v[get_ind(ar[i],0)].push_back({get_ind(ar[i],he[i]),he[i]});
v[get_ind(ar[i],he[i])].push_back({get_ind(ar[i],0),he[i]});
for(ll j=1;j<sz(mp[ar[i]]);j++){
if(mp[ar[i]][j]>he[i]) break;
ll _a = get_ind(ar[i],mp[ar[i]][j]);
ll _b = get_ind(ar[i],mp[ar[i]][j-1]);
ll _c = mp[ar[i]][j] - mp[ar[i]][j-1];
v[_a].push_back({_b,_c});
v[_b].push_back({_a,_c});
}
}
_p=0;
xs.clear();
for(ll i=1;i<=n;i++) xs.insert(ar[i]);
for(auto x:sky){
vector<array<ll,2>> curi;
curi.push_back({ar[x[1]],x[0]});
curi.push_back({ar[x[2]],x[0]});
while(_p<n && he[lol[_p]]<x[0]) xs.erase(xs.find(ar[lol[_p++]]));
auto it = xs.lower_bound(ar[x[1]]);
while(it!=xs.end() && (*it)<=ar[x[2]]){
curi.push_back({(*it),x[0]});
it++;
}
sort(all(curi));
curi.erase(unique(all(curi)),curi.end());
for(ll j=1;j<sz(curi);j++){
ll _a = get_ind(curi[j][0],curi[j][1]);
ll _b = get_ind(curi[j-1][0],curi[j-1][1]);
ll _c = curi[j][0] - curi[j-1][0];
v[_a].push_back({_b,_c});
v[_b].push_back({_a,_c});
}
}
ll ans = dijkstra(get_ind(ar[_st],0),get_ind(ar[_tt],0));
cout << ans << '\n';
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
ll tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/