oj.uz

Submission #898815

# Submission time Handle Problem Language Result Execution time Memory
898815 2024-01-05T06:57:00 Z Samot19 Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 395 ms 65188 KB 
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
#include <utility>
#include <climits>

using namespace std;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int xd, b, w;

bool vis[100005];

pair<int, int> dist[100005];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {

    vector<vector<pair<int, int>>> g(n);

    for(int i=0; i<n; i++) {
        dist[i] = {1000000001, 1000000001};
    }

    for(int i=0; i<m; i++) {
        g[r[i][0]].push_back({r[i][1], l[i]});
        g[r[i][1]].push_back({r[i][0], l[i]});
    }

    for(int i=0; i<k; i++) {
        dist[p[i]] = {0, 0};
        pq.push({0, p[i]});
    }

    while(!pq.empty()) {
        xd = pq.top().second;
        pq.pop();

        if(vis[xd]) continue;

        vis[xd] = true;

        for(auto z : g[xd]) {
            b = z.first;
            w = z.second;

            if(dist[b].first > dist[b].second) {
                swap(dist[b].first, dist[b].second);
            }

            if(max(dist[xd].first, dist[xd].second)+w < dist[b].second) {
                dist[b].second = min(max(dist[xd].first, dist[xd].second)+w, 1000000001);
                if(max(dist[b].second, dist[b].first) < 1000000001) {
                    pq.push({max(dist[b].second, dist[b].first), b});
                }
            }
        }
    }

    return max(dist[0].first, dist[0].second);
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4564 KB Output is correct
12 Correct 3 ms 4912 KB Output is correct
13 Correct 3 ms 4956 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4452 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4564 KB Output is correct
12 Correct 3 ms 4912 KB Output is correct
13 Correct 3 ms 4956 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4452 KB Output is correct
16 Correct 292 ms 60308 KB Output is correct
17 Correct 51 ms 17004 KB Output is correct
18 Correct 63 ms 18236 KB Output is correct
19 Correct 395 ms 65188 KB Output is correct
20 Correct 211 ms 52048 KB Output is correct
21 Correct 27 ms 9072 KB Output is correct
22 Correct 228 ms 48052 KB Output is correct