oj.uz

Submission #689696

# Submission time Handle Problem Language Result Execution time Memory
689696 2023-01-29T06:22:29 Z zeroesandones Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 525 ms 93672 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;

using ll = long long;
using vi = vector<ll>;
using pi = pair<ll, ll>;

#define fr first
#define sc second
#define pb emplace_back

const int mxN = 1e5 + 5;
vector<pi> adj[mxN];
const ll inf = 1e15;

// work backwards maybe?
// start from the exit nodes
// dp[i] = 2nd max of all the nodes we can come from

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    for(int i = 0; i < M; ++i) {
        adj[R[i][0]].pb(R[i][1], L[i]);
        adj[R[i][1]].pb(R[i][0], L[i]);
    }

    priority_queue<pi> pq;
    ll dist[N][2] = {};
    bool vis[N] = {};

    for(int i = 0; i < N; ++i) {
        dist[i][1] = dist[i][0] = inf;
    }

    for(int i = 0; i < K; ++i) {
        dist[P[i]][1] = dist[P[i]][0] = 0;
        pq.emplace(0, P[i]);
    }

    while(!pq.empty()) {
        ll x = pq.top().sc;
        pq.pop();

        if(vis[x]) continue;
        vis[x] = true;

        for(auto [y, w] : adj[x]) {
            ll curr = dist[x][1] + w;
            if(dist[y][0] >= curr) {
                dist[y][1] = dist[y][0];
                dist[y][0] = curr;
                pq.emplace(-dist[y][1], y);
            } else if(dist[y][1] > curr) {
                dist[y][1] = curr;
                pq.emplace(-dist[y][1], y);
            }
        }
    }

    return dist[0][1];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 3 ms 2772 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 3 ms 3028 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 2 ms 2772 KB Output is correct
12 Correct 7 ms 3208 KB Output is correct
13 Correct 4 ms 3284 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2772 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 3 ms 2772 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 3 ms 3028 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 2 ms 2772 KB Output is correct
12 Correct 7 ms 3208 KB Output is correct
13 Correct 4 ms 3284 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2772 KB Output is correct
16 Correct 402 ms 68908 KB Output is correct
17 Correct 94 ms 19860 KB Output is correct
18 Correct 110 ms 22376 KB Output is correct
19 Correct 525 ms 93672 KB Output is correct
20 Correct 258 ms 68164 KB Output is correct
21 Correct 51 ms 10392 KB Output is correct
22 Correct 284 ms 64608 KB Output is correct