Submission #778528

#TimeUsernameProblemLanguageResultExecution timeMemory
778528EliasSky Walking (IOI19_walk)C++17
Compilation error
0 ms0 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>, 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; map<int, int> last_at_height; int i = 0; for (int b : x) { while (active.size() && active.begin()->first < b) { active_by_h.erase({active.begin()->second, active.begin()->first}); active.erase(active.begin()); } for (auto [H, end] : active_by_h) { if (H > int(h[i])) break; int last = last_at_height[H]; 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) { assert(bridges.back().h <= h[i]); 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) { if (H > int(h[i]) break; adj[{b, lasth}].push_back({abs(H - lasth), {b, H}}); adj[{b, H}].push_back({abs(H - lasth), {b, lasth}}); lasth = H; last_at_height[H] = b; } i++; } assert(bridges.size() == 0); priority_queue<tuple<int, int, int>> pq; pq.push(tuple<int, int, int>{0, x[s], 0}); map<pair<int, int>, int> dist; 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}); } } if (dist.count({x[g], 0}) == 0) return -1; 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:25: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]
   25 |  for (int i = 0; i < l.size(); i++)
      |                  ~~^~~~~~~~~~
walk.cpp:67:21: error: expected ';' before 'break'
   67 |    if (H > int(h[i])
      |                     ^
      |                     ;
   68 |     break;
      |     ~~~~~            
walk.cpp:67:10: warning: value computed is not used [-Wunused-value]
   67 |    if (H > int(h[i])
      |        ~~^~~~~~~~~~~
walk.cpp:69:55: error: expected ')' before ';' token
   69 |    adj[{b, lasth}].push_back({abs(H - lasth), {b, H}});
      |                                                       ^
      |                                                       )
walk.cpp:67:7: note: to match this '('
   67 |    if (H > int(h[i])
      |       ^
walk.cpp:69:29: error: could not convert '(& adj.std::map<std::pair<long int, long int>, std::vector<std::pair<long int, std::pair<long int, long int> > > >::operator[](std::pair<long int, long int>(b, lasth)))->std::vector<std::pair<long int, std::pair<long int, long int> > >::push_back(std::pair<long int, std::pair<long int, long int> >(std::abs((H - lasth)), std::pair<long int, long int>(b, (* & H))))' from 'void' to 'bool'
   69 |    adj[{b, lasth}].push_back({abs(H - lasth), {b, H}});
      |    ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
      |                             |
      |                             void