Submission #1242665

#TimeUsernameProblemLanguageResultExecution timeMemory
1242665BoasSky Walking (IOI19_walk)C++20
0 / 100
4098 ms1114112 KiB
#include "walk.h" #include <bits/stdc++.h> using namespace std; #define int long long #define loop(n, i) for (int i = 0; i < n; i++) #define pb push_back #define sz(x) (int)(x).size() typedef pair<int, int> ii; typedef tuple<int, int, int> iii; typedef vector<int> vi; typedef vector<int32_t> vi32; typedef vector<ii> vii; typedef vector<vi> vvi; typedef vector<vii> vvii; typedef set<ii> sii; typedef map<int, int> mii; int INF = 1e18; int min_distance(vi32 x, vi32 h, vi32 l, vi32 r, vi32 y, int32_t s, int32_t g) { int n = sz(x), m = sz(l); vector<map<int, vi>> adj(n); // map<int, int> xToIx; // loop(n, i) xToIx[x[i]] = i; loop(m, i) { for (int p = l[i]; p <= r[i]; p++) { if (h[p] < y[i]) continue; for (int p2 = l[i]; p2 <= r[i]; p2++) { if (h[p2] < y[i]) continue; if (p == p2) continue; adj[p][y[i]].pb(p2); } } } priority_queue<iii, vector<iii>, greater<iii>> q; vector<mii> disList(n); auto dis = [&](int p, int y) -> int { if (disList[p].count(y)) return disList[p][y]; return INF; }; q.push({0, s, 0}); while (!q.empty()) { auto [d, p, y] = q.top(); q.pop(); if (dis(p, y) < d) continue; disList[p][y] = d; for (int p2 : adj[p][y]) { int d2 = d + abs(x[p2] - x[p]); if (d2 < dis(p2, y)) { disList[p2][y] = d2; q.push({d2, p2, y}); } } for (auto [y2, adjY] : adj[p]) { int d2 = d + abs(y2 - y); if (d2 < dis(p, y2)) { disList[p][y2] = d2; q.push({d2, p, y2}); } } } int res = INF; for (auto [y, adjY] : adj[g]) { res = min(res, dis(g, y) + y); } return res; }
#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...