Submission #416367

#TimeUsernameProblemLanguageResultExecution timeMemory
416367idk321Sky Walking (IOI19_walk)C++17
24 / 100
1151 ms347064 KiB
#include "walk.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int M = 2000005; const int N = 100005; const ll INF = 2000000000000000000LL; vector<array<int, 2>> adj[M]; vector<array<int, 2>> isAt[N]; int cnode = 0; ///usr/include/c++/10/bits/stl_heap.h|209|error: ‘bool Comparator::operator()(const std::__debug::array<long long int, 2>&, const std::__debug::array<long long int, 2>&) const’ is private within this context| struct Comparator { bool operator() (const array<ll, 2>& ar1, const array<ll, 2>& ar2) const { return tie(ar1[1], ar1[0]) < tie(ar2[1], ar2[0]); } }; 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 snode = -1; int gnode = -1; for (int i = 0; i < x.size(); i++) { isAt[i].push_back({cnode, 0}); if (i == s) { snode = cnode; } if (i == g) { gnode = cnode; } cnode++; } vector<array<int, 2>> byHeight; for (int i = 0; i < l.size(); i++) { byHeight.push_back({y[i], i}); } sort(byHeight.begin(), byHeight.end()); set<int> ok; for (int i = 0; i < x.size(); i++) ok.insert(i); for (int ci = 0; ci < l.size(); ci++) { int i = byHeight[ci][1]; int prev = -1; for (auto it = ok.lower_bound(l[i]); it != ok.end() && *it <= r[i]; ) { int j = *it; if (h[j] >= y[i]) { adj[cnode].push_back({isAt[j].back()[0], abs(isAt[j].back()[1] - y[i])}); adj[isAt[j].back()[0]].push_back({cnode, abs(isAt[j].back()[1] - y[i])}); isAt[j].push_back({cnode, y[i]}); if (prev != -1) { adj[cnode].push_back({cnode - 1, x[j] - x[prev]}); adj[cnode - 1].push_back({cnode, x[j] - x[prev]}); } prev = j; cnode++; it++; } else { it = ok.erase(it); } } } set<array<ll, 2>, Comparator> sett; sett.insert({snode, 0}); vector<ll> dist(M, INF); dist[snode] = 0; while (!sett.empty()) { auto cur = *sett.begin(); sett.erase(sett.begin()); for (auto next : adj[cur[0]]) { if (cur[1] + next[1] < dist[next[0]]) { if (dist[next[0]] != INF) { sett.erase({next[0], dist[next[0]]}); } dist[next[0]] = cur[1] + next[1]; sett.insert({next[0], cur[1] + next[1]}); } } } if (dist[gnode] == INF) return -1; return dist[gnode]; }

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:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < x.size(); i++)
      |                     ~~^~~~~~~~~~
walk.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int i = 0; i < l.size(); i++)
      |                     ~~^~~~~~~~~~
walk.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int i = 0; i < x.size(); i++) ok.insert(i);
      |                     ~~^~~~~~~~~~
walk.cpp:59:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int ci = 0; ci < l.size(); ci++)
      |                      ~~~^~~~~~~~~~
#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...