| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1057523 |
2024-08-13T20:58:12 Z |
Zicrus |
Sky Walking (IOI19_walk) |
C++17 |
|
91 ms |
119128 KB |
#include <bits/stdc++.h>
#include "walk.h"
using namespace std;
typedef long long ll;
ll n, m;
vector<vector<pair<ll, ll>>> ints; // y, nodeId
vector<pair<ll, pair<ll, ll>>> bridges;
ll cnt;
vector<vector<pair<ll, ll>>> adj;
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
n = x.size(); m = y.size();
cnt = 0;
ints = vector<vector<pair<ll, ll>>>(n);
ints[s].push_back({0, cnt++});
ints[g].push_back({0, cnt++});
bridges = vector<pair<ll, pair<ll, ll>>>(m);
for (int i = 0; i < m; i++) {
bridges[i] = {y[i], {l[i], r[i]}};
}
sort(bridges.begin(), bridges.end());
vector<vector<pair<ll, ll>>> it(m); // x, nodeId
for (int j = 0; j < m; j++) {
pair<ll, ll> p = bridges[j].second;
for (int i = p.first; i <= p.second; i++) {
if (bridges[j].first > h[i]) continue;
it[j].push_back({x[i], cnt});
ints[i].push_back({bridges[j].first, cnt++});
}
}
adj = vector<vector<pair<ll, ll>>>(cnt); // dist, nodeId
for (auto &e : ints) { // SIGNAL 11
for (int i = 0; i < e.size()-1; i++) {
adj[e[i].second].push_back({e[i+1].first - e[i].first, e[i+1].second});
if (n >= 50) throw;
adj[e[i+1].second].push_back({e[i+1].first - e[i].first, e[i].second});
}
}
for (auto &e : it) {
for (int i = 0; i < e.size()-1; i++) {
adj[e[i].second].push_back({e[i+1].first - e[i].first, e[i+1].second});
adj[e[i+1].second].push_back({e[i+1].first - e[i].first, e[i].second});
}
}
priority_queue<pair<ll, ll>> q;
q.push({0, 0});
vector<ll> dist(cnt, 1ll << 62ll);
dist[0] = 0;
vector<bool> vst(cnt);
while (!q.empty()) {
ll cur = q.top().second; q.pop();
if (vst[cur]) continue;
vst[cur] = true;
for (auto &e : adj[cur]) {
dist[e.second] = min(dist[e.second], dist[cur] + e.first);
q.push({-dist[e.second], e.second});
}
}
return dist[1] == 1ll << 62ll ? -1 : dist[1];
}
Compilation message
walk.cpp: In function 'll min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:37:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int i = 0; i < e.size()-1; i++) {
| ~~^~~~~~~~~~~~
walk.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for (int i = 0; i < e.size()-1; i++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Runtime error |
91 ms |
119128 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
24408 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
24408 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
