oj.uz

답안 #1057500

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1057500 2024-08-13T20:41:56 Z Zicrus Sky Walking (IOI19_walk) C++17
0 / 100
 2953 ms 1048576 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) {
    try {
        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) {
            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});
            }
        }
        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];
    }
    catch (exception e) {
        return -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:38:31: 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]
   38 |             for (int i = 0; i < e.size()-1; i++) {
      |                             ~~^~~~~~~~~~~~
walk.cpp:44:31: 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++) {
      |                             ~~^~~~~~~~~~~~
walk.cpp:67:22: warning: catching polymorphic type 'class std::exception' by value [-Wcatch-value=]
   67 |     catch (exception e) {
      |                      ^

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 1 ms 348 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 475 ms 122868 KB Output is correct
4 Correct 448 ms 123988 KB Output is correct
5 Runtime error 104 ms 106320 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 21852 KB Output is correct
2 Correct 2953 ms 798036 KB Output is correct
3 Runtime error 763 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 21852 KB Output is correct
2 Correct 2953 ms 798036 KB Output is correct
3 Runtime error 763 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 1 ms 348 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -