Submission #421453

#TimeUsernameProblemLanguageResultExecution timeMemory
421453MlxaSky Walking (IOI19_walk)C++14
10 / 100
4049 ms153312 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define all(x) x.begin(), x.end() #define mp make_pair #define mt make_tuple0 #define x first #define y second #include "walk.h" namespace my { const int N = 1 << 20; const int INF = 0x3f3f3f3f; const ll LLINF = 0x3f3f3f3f3f3f3f3fLL; struct str_1 { int arr[N]; void upd(int l, int r, int v) { for (int i = l; i <= r; ++i) { arr[i] = v; } } int query(int i) { return arr[i]; } } assigner; struct str_2 { int arr[N]; void upd(int i, int v) { arr[i] = v; } int to_rig(int i, int v) { while (i < N && arr[i] < v) { ++i; } return i; } int to_lef(int i, int v) { while (i >= 0 && arr[i] < v) { --i; } return i; } } gfinder; struct walk { int l, r, y, i; walk(int a, int b, int c) : l(a), r(b), y(c), i(-1) {} }; bool operator<(walk a, walk b) { return a.y < b.y; } vector<walk> was; vector<int> ord[N]; vector<pair<int, int>> pt; map<pair<int, int>, int> ma; vector<pair<int, int>> g[N]; ll dist[N]; int _get_id(int x, int y) { auto p = make_pair(x, y); if (ma.count(p)) { return ma[p]; } else { int v = (int)ma.size(); assert((int)pt.size() < N); pt.emplace_back(x, y); return ma[p] = v; } // int i = (int)(find(all(pt), mp(x, y)) - pt.begin()); // return i; } int get_id(int x, int y) { int i = _get_id(x, y); assert(pt[i].x == x); assert(pt[i].y == y); return i; } void add_edge(int v, int u) { assert(pt[v].x == pt[u].x || pt[v].y == pt[u].y); if (v == u) { return; } // cout << "edge " << v << " " << u << endl; int w = abs(pt[v].x - pt[u].x) + abs(pt[v].y - pt[u].y); // cout << "edge " << pt[v].x << " " << pt[v].y << " " << pt[u].x << " " << pt[u].y << " " << w << endl; g[v].emplace_back(u, w); g[u].emplace_back(v, w); } void vert_edge(int x, int i, int j) { assert(i != -1); // cout << "vert " << x << " " << i << " " << j << endl; if (j == -1) { int v = get_id(x, was[i].y); ord[i].push_back(v); return; } int v = get_id(x, was[i].y); int u = get_id(x, was[j].y); ord[i].emplace_back(v); ord[j].emplace_back(u); add_edge(v, u); } } ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int st, int fi) { using namespace my; int n = (int)x.size(), m = (int)l.size(); for (int i = 0; i < n; ++i) { gfinder.upd(i, h[i]); } vector<walk> temp; for (int i = 0; i < m; ++i) { was.emplace_back(l[i], r[i], y[i]); } was.emplace_back(0, n - 1, 0); sort(all(was)); for (auto e : was) { if (e.l <= st && st <= e.r) { int a = gfinder.to_lef(st, e.y); int b = gfinder.to_rig(st, e.y); assert(e.l <= a && a <= b && b <= e.r); if (e.l < a) { temp.emplace_back(e.l, a, e.y); } if (a < b) { temp.emplace_back(a, b, e.y); } if (b < e.r) { temp.emplace_back(b, e.r, e.y); } } else { temp.push_back(e); } } was = temp; temp.clear(); for (auto e : was) { if (e.l <= fi && fi <= e.r) { int a = gfinder.to_lef(fi, e.y); int b = gfinder.to_rig(fi, e.y); assert(e.l <= a && a <= b && b <= e.r); if (e.l < a) { temp.emplace_back(e.l, a, e.y); } if (a < b) { temp.emplace_back(a, b, e.y); } if (b < e.r) { temp.emplace_back(b, e.r, e.y); } } else { temp.push_back(e); } } was = temp; temp.clear(); assert(is_sorted(all(was))); m = (int)was.size(); for (int i = 0; i < m; ++i) { // cout << was[i].l << " " << was[i].r << " " << was[i].y << endl; was[i].i = i; } assigner.upd(0, n - 1, -1); for (int i = 0; i < m; ++i) { auto e = was[i]; vert_edge(x[e.l], e.i, assigner.query(e.l)); vert_edge(x[e.r], e.i, assigner.query(e.r)); assigner.upd(e.l, e.r, e.i); } assigner.upd(0, n - 1, -1); for (int i = m; i--; ) { auto e = was[i]; int j = assigner.query(e.l); if (j != -1 && h[e.l] >= was[j].y) { vert_edge(x[e.l], e.i, j); } j = assigner.query(e.r); if (j != -1 && h[e.r] >= was[j].y) { vert_edge(x[e.r], e.i, j); } assigner.upd(e.l, e.r, e.i); } for (int i = 0; i < m; ++i) { if (was[i].y == 0) { continue; } sort(all(ord[i]), [&](int a, int b) { return pt[a].x < pt[b].x; }); for (int j = 0; j + 1 < (int)ord[i].size(); ++j) { add_edge(ord[i][j], ord[i][j + 1]); } } int from = get_id(x[st], 0), to = get_id(x[fi], 0); fill_n(dist, N, LLINF); dist[from] = 0; using T = pair<ll, int>; priority_queue<T, vector<T>, greater<T>> q; q.emplace(dist[from], from); // cout << "from " << pt[from].x << " " << pt[from].y << endl; // cout << "to " << pt[to].x << " " << pt[to].y << endl; while (q.size()) { ll d; int v; tie(d, v) = q.top(); q.pop(); if (dist[v] != d) { continue; } for (auto e : g[v]) { int u = e.x, w = e.y; if (dist[u] > dist[v] + w) { dist[u] = dist[v] + w; q.emplace(dist[u], u); } } } if (dist[to] > LLINF / 2) { return -1; } else { return dist[to]; } } #ifdef LC #include "grader.cpp" #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...