| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 145659 | Xylofo | Sky Walking (IOI19_walk) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define eb emplace_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const ll INF =1e18;
#define debug(...) //ignore
template<class T>
auto dijkstra(int source, vector<vector<pair<int, T>>> &g) {
int n = sz(g);
vector<T> dist(n, numeric_limits<T>::max());
vector<pair<int,T> > dad(n, {-1, 0});
priority_queue<pair<T,int> > pq;
dist[source] = 0;
pq.emplace(0,source);
while(!pq.empty()) {
T d; int x;
tie(d,x) = pq.top();
d = -d;
pq.pop();
if(d > dist[x]) continue;
for(auto [y,w] : g[x]) {
if(dist[y] > d + w) {
dist[y] = d + w;
dad[y] = {x, w};
pq.emplace(-dist[y], y);
}
}
}
return pair{dist, dad};
}
ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
int n = sz(x), m = sz(l);
debug(n,m);
auto stALL= [&](){
vector<map<ll,int>> Q;
auto pcomp = [&] (vi idx) {
Q.emplace_back();
int hh = 0;
for(int i : idx) if(h[i] > hh) {
hh = h[i];
Q.back()[hh] = i;
}
};
{ vi ind; rep(i,s,n) ind.emplace_back(i); pcomp(ind); }
{ vi ind; for(int i = s; i >= 0; --i) ind.emplace_back(i); pcomp(ind); }
{ vi ind; rep(i,g,n) ind.emplace_back(i); pcomp(ind); }
{ vi ind; for(int i = g; i >= 0; --i) ind.emplace_back(i); pcomp(ind); }
debug(Q);
map<ll, map<ll, int> > V;
map<int, pair<ll,ll>> iV;
vector<vector<pair<int,ll>>> E;
auto at = [&](int i, int h) {
if (!V[x[i]].count(h)) {
V[x[i]][h] = sz(E);
iV[sz(E)] = {x[i],h};
debug(i,h);
E.emplace_back();
}
return V[x[i]][h];
};
auto edge = [&](int a, int b, ll c) {
E[a].emplace_back(b,c);
E[b].emplace_back(a,c);
};
auto edges = [&](map<ll,int> vert) {
pair<ll,int> a = *vert.begin();
vert.erase(vert.begin());
for(auto b : vert) {
edge(a.second, b.second, b.first-a.first);
a = b;
}
};
at(s,0);
at(g,0);
rep(i,0,m) {
l[i], r[i], y[i];
map<ll, int> vert;
vert[x[l[i]]] = at(l[i], y[i]);
vert[x[r[i]]] = at(r[i], y[i]);
for(auto &q: Q) {
auto it = q.lower_bound(y[i]);
if(it == q.end()) continue;
int j = it->second;
debug("HEJ", i,j);
if(l[i] <= j && j <= r[i]) vert[x[j]] = at(j, y[i]);
}
edges(vert);
}
for(auto v: V) edges(v.second);
debug(sz(E))
auto[dist, dad] = dijkstra(at(s,0),E);
for(int q = at(g,0); dad[q].first != -1; q = dad[q].first) {
debug(iV[q]);
}
ll ans = dist[at(g, 0)];
if (ans >= INF) ans = -1;
return ans;
};
return stALL();
}