| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 281683 | Vimmer | Sky Walking (IOI19_walk) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}