Submission #417835

#TimeUsernameProblemLanguageResultExecution timeMemory
417835idk321Sky Walking (IOI19_walk)C++17
0 / 100
246 ms82112 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) { if (s > g) { swap(s, 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()); for (int ci = 0; ci < l.size(); ci++) { int i = byHeight[ci][1]; int prev = -1; vector<int> build; build.push_back(l[i]); if (l[i]< s && s < r[i] && y[i] <= h[s]) build.push_back(s); if (l[i]< g && g < r[i] && y[i] <= h[g]) build.push_back(g); build.push_back(r[i]); for (int cur : build) { adj[cnode].push_back({isAt[cur].back()[0], y[i] - isAt[cur].back()[1]}); adj[isAt[cur].back()[0]].push_back({cnode, y[i] - isAt[cur].back()[1]}); isAt[cur].push_back({cnode, y[i]}); if (prev != -1) { adj[cnode].push_back({cnode - 1, x[cur] - x[prev]}); adj[cnode - 1].push_back({cnode, x[cur] - x[prev]}); } prev = cur; cnode++; } } priority_queue<array<ll, 2>, vector<array<ll, 2>>, Comparator> pq; pq.push({snode, 0}); vector<ll> dist(M, INF); while (!pq.empty()) { auto cur = pq.top(); pq.pop(); if (dist[cur[0]] != INF) continue; dist[cur[0]] = cur[1]; for (auto next : adj[cur[0]]) { if (dist[next[0]] == INF) { pq.push({next[0], next[1] + cur[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:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 0; i < x.size(); i++)
      |                     ~~^~~~~~~~~~
walk.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i = 0; i < l.size(); i++)
      |                     ~~^~~~~~~~~~
walk.cpp:64:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     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...