| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 430642 | saleh | 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 "walk.h"
#include <bits/stdc++.h>
#define int long long
#define ft first
#define sd second
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 100 * 1000 + 23, MAXV = 1000 * 1000 + 23, MAXE = 4000 * 1000 + 23, INF = 1e15;
int n, m, cnt, dis[MAXV];
vector<int> add[MAXN], del[MAXN], pt[MAXN];
set<pii> s;
map<int, int> mp[MAXN];
vector<pii> pts, g[MAXV];
void dij(int v) {/*
for (int i = 0; i < cnt; i++) {
cout << "\\" << i << ": " << pts[i].ft << ' ' << pts[i].sd << endl << '\t';
for (auto j : g[i]) cout << j.ft << ' ' << j.sd << '\t';
cout << endl;
}*/
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, v});
for (int i = 0; i < cnt; i++) dis[i] = INF;
dis[v] = 0;
while (!pq.empty()) {
pii x = pq.top();
pq.pop();
if (x.ft > dis[x.sd]) continue;
for (auto i : g[x.sd]) if (dis[i.ft] > dis[x.sd] + i.sd) {
dis[i.ft] = dis[x.sd] + i.sd;
pq.push({dis[i.ft], i.ft});
}
}
}
long long min_distance(vector<int32_t> x, vector<int32_t> h, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int ss, int gg) {
n = x.size();
m = l.size();
for (int i = 0; i < m; i++) add[l[i]].push_back(i), del[r[i]].push_back(i);
for (int j = 0; j < n; j++) {
for (auto i : add[j]) s.insert({y[i], i});
pii prev = {-1, -1};
for (auto i : s) {
if (i.ft > h[j]) break;
pts.push_back({i.sd, j});
mp[i.sd][j] = cnt++;
pt[i.sd].push_back(j);
if (prev.sd != -1) g[cnt - 1].push_back({cnt - 2, i.ft - prev.ft}), g[cnt - 2].push_back({cnt - 1, i.ft - prev.ft});
prev = i;
}
for (auto i : del[j]) s.erase({y[i], i});
}
for (int i = 0; i < m; i++) for (int j = 1; j < (int)pt[i].size(); j++)
g[mp[i][pt[i][j - 1]]].push_back({mp[i][pt[i][j]], x[pt[i][j]] - x[pt[i][j - 1]]}), g[mp[i][pt[i][j]]].push_back({mp[i][pt[i][j - 1]], x[pt[i][j]] - x[pt[i][j - 1]]});
dij(ss);
return dis[gg];
}/*
int32_t main() { cout << min_distance({0, 4, 5, 6, 9},
{6, 6, 6, 6, 6},
{3, 1, 0},
{4, 3, 2},
{1, 3, 6},
0, 4); }*/