제출 #951352

#제출 시각아이디문제언어결과실행 시간메모리
951352qinSky Walking (IOI19_walk)C++17
24 / 100
4086 ms669796 KiB
#include <bits/stdc++.h> #define fi first #define se second #define ssize(x) int(x.size()) #define pn printf("\n") #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(), x.rend() #define vv vector using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<int, ll> pil; typedef pair<ll, int> pli; int inf = 2e09; ll infll = 2e18; int mod = 119<<23|1; ll min_distance(vv<int> x, vv<int> h, vv<int> l, vv<int> r, vv<int> y, int s, int e){ int n = ssize(x), m = ssize(y); vv<set<int>> beg(n), ed(n); for(int i = 0; i < m; ++i) beg[l[i]].emplace(y[i]), ed[r[i]].emplace(y[i]); for(int i = 0; i < n; ++i){ vv<int> to_remove; for(int u : beg[i]){ auto it = lower_bound(all(ed[i]), u); if(it != ed[i].end() && *it == u) to_remove.emplace_back(u); } for(int u : to_remove) beg[i].erase(u), ed[i].erase(u); } set<int> active; vv<vv<pii>> g(1); int cnt = 0; map<pii, int> mp; int a = -1, b = -1; for(int i = 0; i < n; ++i){ vv<pii> nr; if(i == s || i == e){ nr.emplace_back(++cnt, 0), g.emplace_back(vv<pii>()); if(a == -1) a = cnt; else b = cnt; mp[pii(i, 0)] = cnt; } for(int u : beg[i]) active.emplace(u); for(int u : active){ if(u > h[i]) break; mp[pii(i, u)] = ++cnt, nr.emplace_back(cnt, u), g.emplace_back(vv<pii>()); } for(int u : ed[i]) active.erase(u); //~ printf("%d:\n", i); for(int j = 0; j < ssize(nr)-1; ++j) g[nr[j].fi].emplace_back(nr[j+1].fi, abs(nr[j].se-nr[j+1].se)), g[nr[j+1].fi].emplace_back(nr[j].fi, abs(nr[j].se-nr[j+1].se)); //~ pn; } map<int, int> last; for(int i = 0; i < n; ++i){ //~ printf("%d:\n", i); for(int u : active){ if(u > h[i]) break; //~ printf("%d %d, ", u, abs(x[last[u]]-x[i])); g[mp[pii(i, u)]].emplace_back(mp[pii(last[u], u)], abs(x[last[u]]-x[i])), g[mp[pii(last[u], u)]].emplace_back(mp[pii(i, u)], abs(x[last[u]]-x[i])); last[u] = i; } //~ pn; for(int u : beg[i]) active.emplace(u), last[u] = i; for(int u : ed[i]) active.erase(u), last[u] = 0; } n = ssize(g)-1; vv<ll> dist(n+1, infll); dist[a] = 0; priority_queue<pli> pq; pq.emplace(0, a); while(ssize(pq)){ int X = pq.top().se; ll d = -pq.top().fi; pq.pop(); if(dist[X] != d) continue; for(pii u : g[X]) if(d+u.se < dist[u.fi]) dist[u.fi] = d+u.se, pq.emplace(-dist[u.fi], u.fi); } if(dist[b] == infll) return -1; else return dist[b]; return 0; } #ifdef LOCAL signed main(){ int T = 1; for(++T; --T; ){ int n, m, s, g; scanf("%d%d", &n, &m); vv<int> x(n), h(n), l(m), r(m), y(m); for(int i = 0; i < n; ++i) scanf("%d", &x[i]); for(int i = 0; i < n; ++i) scanf("%d", &h[i]); for(int i = 0; i < m; ++i) scanf("%d", &l[i]); for(int i = 0; i < m; ++i) scanf("%d", &r[i]); for(int i = 0; i < m; ++i) scanf("%d", &y[i]); scanf("%d%d", &s, &g); ll result = min_distance(x, h, l, r, y, s, g); printf("%lld\n", result); } return 0; } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...