oj.uz

Submission #1033497

# Submission time Handle Problem Language Result Execution time Memory
1033497 2024-07-25T00:12:45 Z ArthuroWich Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 2 ms 1116 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    long long int n, m;
    n = N;
    m = M;
    vector<long long int> vis(n, 0), bestdist(n, INT64_MAX), seconddist(n, INT64_MAX), proc(n, 0);
    vector<vector<pair<long long int, long long int>>> adj(n+1);
    for (long long int i = 0; i < m; i++) {
        adj[R[i][0]].push_back({R[i][1], L[i]});
        adj[R[i][1]].push_back({R[i][0], L[i]});
    }
    set<pair<long long int, long long int>> pq;
    for (long long int i = 0; i < K; i++) {
        pq.insert({0, P[i]});
    }
    while(!pq.empty()) {
        auto [d, a] = *pq.begin();
        pq.erase(pq.begin());
        d = abs(d);
        for (auto [b, w] : adj[a]) {
            vis[b]++;
            if (vis[b] == 1) {
                bestdist[b] = d+w;
            } else if (vis[b] == 2) {
                long long int v = bestdist[b];
                bestdist[b] = min(v, d+w);
                seconddist[b] = max(v, d+w);
                pq.insert({max(v, d+w), b});
            } else {
                if (d+w > seconddist[b]) {
                    continue;
                }
                pq.erase({seconddist[b], b});
                if (d+w < bestdist[b]) {
                    seconddist[b] = bestdist[b];
                    bestdist[b] = d+w;
                } else {
                    seconddist[b] = d+w;
                }
                pq.insert({seconddist[b], b});
            }
        }
    }
    return seconddist[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 2 ms 1072 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Incorrect 0 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 2 ms 1072 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Incorrect 0 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -