Submission #1071534

#TimeUsernameProblemLanguageResultExecution timeMemory
1071534Gromp15Sky Walking (IOI19_walk)C++17
24 / 100
4067 ms685404 KiB
#include <bits/stdc++.h> #define ll long long #define ar array #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #include "walk.h" using namespace std; template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } const ll INF = 1e18; long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) { int n = sz(x), m = sz(l); vector<int> idx(n); iota(all(idx), 0); sort(all(idx), [&](int x, int y) { return h[x] > h[y]; }); vector<int> idx2(m); iota(all(idx2), 0); sort(all(idx2), [&](int X, int Y) { return y[X] > y[Y]; }); set<int> who; vector<ar<int, 3>> edges; for (int i = 0, on = 0; i < m; i++) { int L = l[idx2[i]], R = r[idx2[i]], H = y[idx2[i]]; while (on < n && h[idx[on]] >= H) { who.insert(idx[on++]); } int lst = -1; auto it1 = who.lower_bound(L); if (it1 == who.end() || *it1 > R) continue; lst = *it1; while (1) { auto it = who.upper_bound(lst); if (it == who.end() || *it > R) break; edges.push_back({lst, *it, H}); lst = *it; } } vector<vector<int>> nodes(n); vector<map<int, vector<int>>> adj(n); for (auto [l, r, H] : edges) { nodes[l].emplace_back(H); nodes[r].emplace_back(H); adj[l][H].push_back(r); adj[r][H].push_back(l); } nodes[s].emplace_back(0); nodes[g].emplace_back(0); for (int i = 0; i < n; i++) { sort(all(nodes[i])); nodes[i].erase(unique(all(nodes[i])), nodes[i].end()); } vector<map<int, ll>> dist(n); dist[s][0] = 0; priority_queue<ar<ll, 3>, vector<ar<ll, 3>>, greater<ar<ll, 3>>> q; q.push({0, s, 0}); auto rlx = [&](int v1, int x1, int v2, int x2) { ll new_dist = dist[v1][x1] + abs(x[v1] - x[v2]) + abs(x1 - x2); if (!dist[v2].count(x2) || dist[v2][x2] > new_dist) { dist[v2][x2] = new_dist; q.push({dist[v2][x2], v2, x2}); } }; while (q.size()) { auto [cost, v, i] = q.top(); q.pop(); if (cost != dist[v][i]) continue; auto it = upper_bound(all(nodes[v]), i); if (it != nodes[v].end() && *it <= h[v]) { rlx(v, i, v, *it); } assert(it != nodes[v].begin()); it--; if (it != nodes[v].begin() && i <= h[v]) { rlx(v, i, v, *prev(it)); } for (int x : adj[v][i]) { rlx(v, i, x, i); } } return dist[g].count(0) ? dist[g][0] : -1; }
#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...