oj.uz

Submission #852331

# Submission time Handle Problem Language Result Execution time Memory
852331 2023-09-21T15:38:48 Z uped Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 656 ms 77828 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[]) {
    vector<vector<pair<int, int>>> adj(N);
    for (int i = 0; i < M; ++i) {
        adj[R[i][0]].emplace_back(R[i][1], L[i]);
        adj[R[i][1]].emplace_back(R[i][0], L[i]);
    }
    priority_queue<pair<int, int>> pq;
    vector<pair<int, int>> distance(N, {-1, -1});
    vector<bool> is_exit(N);
    for (int i = 0; i < K; ++i) {
        is_exit[P[i]] = true;
        pq.emplace(0, P[i]);
        distance[P[i]] = {0, 0};
    }
    while (!pq.empty()) {
        auto [dist, a] = pq.top(); pq.pop();
        auto& [min, min2] = distance[a];
        if (min == -1 || -dist < min) {
            min2 = min;
            min = -dist;
        } else if (min2 == -1 || -dist < min2) {
            min2 = -dist;
        } else if (!is_exit[a]) {
            continue;
        }
        if (min2 == -1) continue;
        for (auto [b, w] : adj[a]) {
            if (!is_exit[b]) {
                pq.emplace((min2 + w) * -1, b);
            }
        }
    }
    return distance[0].second;
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:22:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |         auto [dist, a] = pq.top(); pq.pop();
      |              ^
crocodile.cpp:23:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |         auto& [min, min2] = distance[a];
      |               ^
crocodile.cpp:33:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |         for (auto [b, w] : adj[a]) {
      |                   ^

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4560 KB Output is correct
9 Correct 4 ms 4700 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 6 ms 5212 KB Output is correct
13 Correct 5 ms 5212 KB Output is correct
14 Correct 1 ms 4544 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4560 KB Output is correct
9 Correct 4 ms 4700 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 6 ms 5212 KB Output is correct
13 Correct 5 ms 5212 KB Output is correct
14 Correct 1 ms 4544 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 604 ms 73224 KB Output is correct
17 Correct 69 ms 15440 KB Output is correct
18 Correct 85 ms 16976 KB Output is correct
19 Correct 656 ms 77828 KB Output is correct
20 Correct 448 ms 65032 KB Output is correct
21 Correct 34 ms 9048 KB Output is correct
22 Correct 425 ms 46760 KB Output is correct