| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 736942 |
2023-05-06T11:32:33 Z |
finn__ |
Sky Walking (IOI19_walk) |
C++17 |
|
45 ms |
7780 KB |
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
using L = long long;
vector<size_t> last_node;
vector<vector<pair<size_t, L>>> G;
vector<pair<L, L>> p;
vector<L> d;
vector<pair<size_t, bool>> events;
void split_walks(vector<int> l, vector<int> r, vector<int> y, int j)
{
size_t const m = l.size();
vector<size_t> to_erase;
for (size_t i = 0; i < m; ++i)
if (l[i] < j && j < r[i])
{
to_erase.push_back(i);
}
for (size_t &i : to_erase)
{
swap(l[i], l.back()), l.pop_back();
swap(r[i], r.back()), r.pop_back();
swap(y[i], y.back()), y.pop_back();
}
}
L min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r,
vector<int> y, int s, int g)
{
size_t const n = x.size(), m = l.size();
last_node.resize(m);
fill(last_node.begin(), last_node.end(), SIZE_MAX);
for (size_t i = 0; i < m; ++i)
events.emplace_back(i, 0), events.emplace_back(i, 1);
sort(events.begin(), events.end(), [&](auto const &u, auto const &v)
{ int const a = u.second ? r[u.first] : l[u.first],
b = v.second ? r[v.first] : l[v.first];
return a == b ? !u.second && v.second : a < b; });
auto compare_segment_height = [&](size_t const &i, size_t const &j)
{ return y[i] < y[j]; };
multiset<size_t, decltype(compare_segment_height)> segments(compare_segment_height);
map<pair<L, L>, size_t> nodes;
auto get_node = [&](L const &i, L const &j)
{
auto it = nodes.find({i, j});
if (it != nodes.end())
return it->second;
nodes[{i, j}] = G.size();
p.emplace_back(i, j);
G.emplace_back();
return G.size() - 1;
};
for (auto const &[i, b] : events)
{
size_t const curr_node = get_node(b ? x[r[i]] : x[l[i]], y[i]);
if (last_node[i] != SIZE_MAX)
{
G[curr_node].emplace_back(last_node[i], p[curr_node].first - p[last_node[i]].first);
G[last_node[i]].emplace_back(curr_node, p[curr_node].first - p[last_node[i]].first);
}
last_node[i] = curr_node;
if (b)
segments.erase(i);
auto it = segments.upper_bound(i);
if (it != segments.end() && h[b ? r[i] : l[i]] >= y[*it])
{
size_t const neighbor = get_node(b ? x[r[i]] : x[l[i]], y[*it]);
G[curr_node].emplace_back(neighbor, y[*it] - y[i]);
G[neighbor].emplace_back(curr_node, y[*it] - y[i]);
G[neighbor].emplace_back(last_node[*it], p[neighbor].first - p[last_node[*it]].first);
G[last_node[*it]].emplace_back(neighbor, p[neighbor].first - p[last_node[*it]].first);
last_node[*it] = neighbor;
}
it = segments.lower_bound(i);
if (!segments.empty() && it != segments.begin() && p[*prev(it)].second < y[i])
{
--it;
size_t const neighbor = get_node(b ? x[r[i]] : x[l[i]], y[*it]);
G[curr_node].emplace_back(neighbor, y[i] - y[*it]);
G[neighbor].emplace_back(curr_node, y[i] - y[*it]);
G[neighbor].emplace_back(last_node[*it], p[neighbor].first - p[last_node[*it]].first);
G[last_node[*it]].emplace_back(neighbor, p[neighbor].first - p[last_node[*it]].first);
last_node[*it] = neighbor;
}
if (!b)
segments.insert(i);
}
priority_queue<pair<L, size_t>> q;
d.resize(G.size());
fill(d.begin(), d.end(), LLONG_MAX);
for (size_t i = 0; i < G.size(); ++i)
if (p[i].first == x[s])
d[i] = p[i].second, q.emplace(-d[i], i);
while (!q.empty())
{
auto const [f, u] = q.top();
q.pop();
if (-f != d[u])
continue;
for (auto const &[v, w] : G[u])
if (-f + w < d[v])
{
d[v] = -f + w;
q.emplace(-d[v], v);
}
}
L min_distance = LLONG_MAX;
for (size_t i = 0; i < G.size(); ++i)
if (p[i].first == x[g] && d[i] != LLONG_MAX)
min_distance = min(min_distance, d[i] + p[i].second);
return min_distance == LLONG_MAX ? -1 : min_distance;
}
Compilation message
walk.cpp: In function 'L min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:32:18: warning: unused variable 'n' [-Wunused-variable]
32 | size_t const n = x.size(), m = l.size();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
45 ms |
7780 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
45 ms |
7780 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
