This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 > 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 > 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});
}
}
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++)
| ~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |