oj.uz

Submission #406478

# Submission time Handle Problem Language Result Execution time Memory
406478 2021-05-17T16:06:58 Z Falcon Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 869 ms 96372 KB 
#include "crocodile.h"
#include <vector>
#include <queue>
#include <array>

using namespace std;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    vector<vector<pair<int, long long>>> adj(N);
    for(int i{}; 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]});
    }
    
    priority_queue<pair<long long, int>,
                   vector<pair<long long, int>>,
                   greater<pair<long long, int>>> pq;

    vector<long long> dist(N, -1);
    vector<int> processed_neighbours(N);
    vector<array<long long, 2>> paths(N);
    vector<bool> processed(N);

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

    auto update = [&](int u, long long d) {
        if(processed[u]) return;
        switch(processed_neighbours[u]) {
            case 0:
                paths[u][0] = d;
                break;
            case 1:
                paths[u][1] = d;
                if(paths[u][1] < paths[u][0])
                    swap(paths[u][1], paths[u][0]);
                pq.push({paths[u][1], u});
                break;
            default:
                if(d < paths[u][1])
                    paths[u][1] = d;
                if(paths[u][1] < paths[u][0])
                    swap(paths[u][1], paths[u][0]);
                pq.push({paths[u][1], u});
                break;
        }
        ++processed_neighbours[u];
    };

    while(!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if(processed[u])
            continue;
        processed[u] = true;
        dist[u] = d;
        for(auto [v, w]: adj[u])
            update(v, d + w);
    }

    return int(dist[0]);
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 432 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 6 ms 1228 KB Output is correct
13 Correct 5 ms 1228 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 432 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 6 ms 1228 KB Output is correct
13 Correct 5 ms 1228 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 762 ms 96372 KB Output is correct
17 Correct 87 ms 18756 KB Output is correct
18 Correct 117 ms 21156 KB Output is correct
19 Correct 869 ms 94524 KB Output is correct
20 Correct 503 ms 73992 KB Output is correct
21 Correct 44 ms 8360 KB Output is correct
22 Correct 466 ms 63132 KB Output is correct