Submission #778498

#TimeUsernameProblemLanguageResultExecution timeMemory
778498EliasSky Walking (IOI19_walk)C++17
0 / 100
2064 ms1048576 KiB
#ifndef _DEBUG #include "walk.h" #endif #include <bits/stdc++.h> using namespace std; #define int int64_t struct Bridge { int l, r, h; bool operator<(Bridge other) { return vector<int>{l, r, h} < vector<int>{other.l, other.r, other.h}; } }; long long min_distance(std::vector<signed> x, std::vector<signed> h, std::vector<signed> l, std::vector<signed> r, std::vector<signed> y, signed s, signed g) { map<pair<int, int>, int> dist; map<pair<int, int>, vector<pair<int, pair<int, int>>>> adj; vector<Bridge> bridges; for (int i = 0; i < l.size(); i++) { bridges.push_back({x[l[i]], x[r[i]], y[i]}); } sort(bridges.begin(), bridges.end()); reverse(bridges.begin(), bridges.end()); set<pair<int, int>> active; set<pair<int, int>> active_by_h; int last = -1; for (int b : x) { while (active.size() && active.begin()->first < b) { active_by_h.erase({active.begin()->first, active.begin()->second}); active.erase(active.begin()); } if (last != -1) for (auto [end, h] : active) { adj[{b, h}].push_back({abs(last - b), {last, h}}); adj[{last, h}].push_back({abs(last - b), {b, h}}); } while (bridges.size() && bridges.back().l <= b) { active.insert({bridges.back().r, bridges.back().h}); active_by_h.insert({bridges.back().h, bridges.back().r}); bridges.pop_back(); } int lasth = 0; for (auto [h, end] : active_by_h) { adj[{b, lasth}].push_back({abs(h - lasth), {b, h}}); adj[{b, h}].push_back({abs(h - lasth), {b, lasth}}); lasth = h; } last = b; } priority_queue<tuple<int, int, int>> pq; pq.push(tuple<int, int, int>{0, s, 0}); while (pq.size()) { auto [d, px, py] = pq.top(); pq.pop(); if (dist.count({px, py})) continue; dist[{px, py}] = -d; for (auto [plusd, c] : adj[{px, py}]) { if (dist.count(c) == 0) pq.push(tuple<int, int, int>{d - plusd, c.first, c.second}); } } return dist[{x[g], 0}]; } #ifdef _DEBUG signed main() { signed n, m; assert(2 == scanf("%d%d", &n, &m)); vector<signed> x(n), h(n); for (signed i = 0; i < n; i++) assert(2 == scanf("%d%d", &x[i], &h[i])); vector<signed> l(m), r(m), y(m); for (signed i = 0; i < m; i++) assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i])); signed s, g; assert(2 == scanf("%d%d", &s, &g)); fclose(stdin); long long result = min_distance(x, h, l, r, y, s, g); cerr << result << "\n"; fclose(stdout); return 0; } #endif

Compilation message (stderr)

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for (int i = 0; i < l.size(); i++)
      |                  ~~^~~~~~~~~~
#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...