oj.uz

Submission #1111265

# Submission time Handle Problem Language Result Execution time Memory
1111265 2024-11-11T23:19:54 Z ArtistWall Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 336 ms 65436 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define pb push_back
#define ins insert
#define f first 
#define s second 

int travel_plan(int N, int M, int R[][2], 
    int L[], int k, int p[]) {
    const ll INF = 1e18;
    int n = N, m = M;
    vector<vector<pii>> adj(n);
    for (int i = 0; i < m; i++) {
        int x = R[i][0], y = R[i][1],
            w = L[i];
        adj[x].pb({y, w});
        adj[y].pb({x, w});
    }
    vector<vector<ll>> dist(2, 
        vector<ll>(n, INF));
    priority_queue<pll> pq;
    for (int i = 0; i < k; i++) {
        pq.push({0, p[i]});
        dist[0][p[i]] = 0;
        dist[1][p[i]] = 0;
    }
    while (!pq.empty()) {
        auto N = pq.top(); pq.pop();
        ll u = N.s, t = -N.f;
        if (dist[1][u] != t) {
            continue;
        }
        for (auto [v, w] : adj[u]) {
            if (t + w < dist[0][v]) {
                if (dist[0][v] != dist[1][v]) {
                    pq.push({-dist[0][v], v});
                }
                swap(dist[0][v], dist[1][v]);
                dist[0][v] = t + w;
            } else if (t + w < dist[1][v]) {
                dist[1][v] = t + w;
                pq.push({-dist[1][v], v});
            }
        }
    }
    return (int) dist[1][0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Correct 1 ms 4432 KB Output is correct
5 Correct 2 ms 4432 KB Output is correct
6 Correct 1 ms 4432 KB Output is correct
7 Correct 1 ms 4432 KB Output is correct
8 Correct 2 ms 4432 KB Output is correct
9 Correct 3 ms 4688 KB Output is correct
10 Correct 2 ms 4432 KB Output is correct
11 Correct 2 ms 4432 KB Output is correct
12 Correct 4 ms 4944 KB Output is correct
13 Correct 3 ms 4944 KB Output is correct
14 Correct 2 ms 4432 KB Output is correct
15 Correct 2 ms 4432 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Correct 1 ms 4432 KB Output is correct
5 Correct 2 ms 4432 KB Output is correct
6 Correct 1 ms 4432 KB Output is correct
7 Correct 1 ms 4432 KB Output is correct
8 Correct 2 ms 4432 KB Output is correct
9 Correct 3 ms 4688 KB Output is correct
10 Correct 2 ms 4432 KB Output is correct
11 Correct 2 ms 4432 KB Output is correct
12 Correct 4 ms 4944 KB Output is correct
13 Correct 3 ms 4944 KB Output is correct
14 Correct 2 ms 4432 KB Output is correct
15 Correct 2 ms 4432 KB Output is correct
16 Correct 279 ms 57484 KB Output is correct
17 Correct 49 ms 16968 KB Output is correct
18 Correct 57 ms 18476 KB Output is correct
19 Correct 336 ms 65436 KB Output is correct
20 Correct 212 ms 47432 KB Output is correct
21 Correct 26 ms 9568 KB Output is correct
22 Correct 199 ms 45340 KB Output is correct