oj.uz

Submission #816244

# Submission time Handle Problem Language Result Execution time Memory
816244 2023-08-09T04:34:25 Z jophyyjh Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 519 ms 71392 KB 
/**
 * Essentially a variant of Dijkstra's algorithm. The proof can be left as an exercise.
 * 
 * Time Complexity: O(n + m * log(m))           (Dijkstra)
 * Implementation 1                 (Full solution)
*/

#include <bits/stdc++.h>
#include "crocodile.h"

typedef long long   ll;
typedef std::vector<int>    vec;

const ll INF = 0x3f3f3f3f3f3f3f;


struct edge_t {
    int node, w;
};
typedef std::vector<edge_t> adj_list_t;

struct dist_info_t {
    int node;
    ll dist;
};

inline bool operator<(const dist_info_t& d1, const dist_info_t& d2) {
    return d1.dist > d2.dist;
}

int travel_plan(int n, int m, int edges[][2], int w[], int K, int P[]) {
    std::vector<adj_list_t> graph(n);
    for (int k = 0; k < m; k++) {
        graph[edges[k][0]].push_back(edge_t{edges[k][1], w[k]});
        graph[edges[k][1]].push_back(edge_t{edges[k][0], w[k]});
    }

    std::vector<ll> time(n, INF);
    std::priority_queue<dist_info_t> pq;
    vec wait(n, 2);
    for (int i = 0; i < K; i++) {
        time[P[i]] = 0, wait[P[i]] = 1;
        pq.push(dist_info_t{P[i], 0});
    }
    while (!pq.empty() && wait[0] > 0) {
        dist_info_t t = pq.top();
        pq.pop();
        if (wait[t.node] == 0)
            continue;
        time[t.node] = t.dist, wait[t.node]--;
        if (wait[t.node] == 0) {
            for (const edge_t& e : graph[t.node]) {
                if (wait[e.node] > 0)
                    pq.push(dist_info_t{e.node, time[t.node] + e.w});
            }
        }
    }
    assert(time[0] < INF);
    return time[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 392 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 3 ms 1108 KB Output is correct
13 Correct 3 ms 1252 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 392 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 3 ms 1108 KB Output is correct
13 Correct 3 ms 1252 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 357 ms 71392 KB Output is correct
17 Correct 57 ms 14104 KB Output is correct
18 Correct 87 ms 15560 KB Output is correct
19 Correct 519 ms 65556 KB Output is correct
20 Correct 253 ms 57352 KB Output is correct
21 Correct 35 ms 6092 KB Output is correct
22 Correct 318 ms 36912 KB Output is correct