| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 281683 | Vimmer | Sky Walking (IOI19_walk) | C++14 | 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>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100001
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <int, int> ptr;
typedef array <int, 3> a3;
vector <vector <int> > g;
vector <a3> edge;
vector <int> nums[N], who[N], db[N];
vector <ll> dst;
gp_hash_table <int, int> idr[N];
void add(int a, int b, int cost)
{
g[a].pb(sz(edge));
g[b].pb(sz(edge));
edge.pb({a, b, cost});
}
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int to)
{
int n = sz(x);
int m = sz(l);
set <pair <int, int> > st; st.clear();
for (int j = 0; j < m; j++)
{db[l[j]].pb(j); del[r[j]].pb(j);}
for (int i = 0; i < n; i++)
{
for (auto j : db[i])
st.insert({y[j], j});
auto it = st.upper_bound(ptr(h[i], 1e9));
if (it != st.begin())
{
it--;
while (1)
{
nums[i].pb((*it).S);
if (it == st.begin()) break;
it--;
}
}
for (auto j : del[i])
st.erase({y[j], j});
}
int id = 0;
ll ans = 1e18;
set <pair <ll, int> > str;
set <pair <int, int> > se; se.clear();
for (int i = 0; i < n; i++)
for (auto j : nums[i])
{
if (i == s) se.insert({id, y[j]});
idr[i][j] = id++;
g.emplace_back();
dst.pb(-1);
for (auto jr : nums[i])
{
if (jr == j) break;
add(id - 1, idr[i][jr], abs(y[jr] - y[j]));
}
if (to == i) {dst[id - 1] = 0; str.insert({y[j], id - 1});}
}
for (int i = 0; i < n; i++)
for (auto j : nums[i])
{
for (auto I : who[j])
add(idr[i][j], idr[I][j], abs(x[i] - x[I]));
who[j].pb(i);
}
while (sz(str))
{
pair <ll, int> pt = *str.begin(); str.erase(str.begin());
if (pt.F >= ans) return ans;
auto it = se.upper_bound(ptr(pt.S, 1e9 + 1e9));
if (it != se.begin())
{
it--;
if ((*it).F == pt.S) {ans = min(ans, pt.F + (*it).S); se.erase(it); if (sz(se) == 0) return ans;}
}
for (auto ip : g[pt.S])
{
a3 itr = edge[ip];
ll s = pt.F + itr[2];
if (itr[0] == pt.S) swap(itr[0], itr[1]);
if (dst[itr[0]] != - 1 && dst[itr[0]] <= s) continue;
if (ans <= s) continue;
str.erase({dst[itr[0]], itr[0]});
dst[itr[0]] = s;
str.insert({s, itr[0]});
}
}
if (ans == 1e18) return -1;
return ans;
}