oj.uz

Submission #1057524

# Submission time Handle Problem Language Result Execution time Memory
1057524 2024-08-13T20:59:25 Z Zicrus Sky Walking (IOI19_walk) C++17
0 / 100
 98 ms 119356 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++) {
            ll dist = e[i+1].first - e[i].first;
            if (n >= 50) throw;
            adj[e[i].second].push_back({dist, e[i+1].second});
            adj[e[i+1].second].push_back({dist, 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:45: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]
   45 |         for (int i = 0; i < e.size()-1; i++) {
      |                         ~~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Runtime error 1 ms 348 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Runtime error 98 ms 119356 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 24408 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 24408 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Runtime error 1 ms 348 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -