oj.uz

Submission #512409

# Submission time Handle Problem Language Result Execution time Memory
512409 2022-01-16T10:40:50 Z ronnith Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 619 ms 63328 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

const int max_n = (int)1e5;
int n, m, k;
vector<pair<int, int>> adj[max_n];
int D[max_n];
vector<int> mn2[max_n];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    n = N;
    m = M;
    k = K;
    for (int i = 0; i < n; i ++) {
        D[i] = INT_MAX;
        adj[i].clear();
        mn2[i].clear();
    }
    for (int i = 0; i < m; i ++) {
        adj[R[i][0]].push_back(make_pair(R[i][1], L[i]));
        adj[R[i][1]].push_back(make_pair(R[i][0], L[i]));
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (int i = 0; i < k; i ++) {
        D[P[i]] = 0;
        pq.push(make_pair(D[P[i]], P[i]));
    }
    while ((int)pq.size()) {
        auto x = pq.top();
        pq.pop();
        if (x.first != D[x.second]) continue;
        for (auto& e : adj[x.second]) {
            mn2[e.first].push_back(D[x.second] + e.second);
            sort(mn2[e.first].begin(), mn2[e.first].end());
            if ((int)mn2[e.first].size() > 2) {
                mn2[e.first].pop_back();
            }
            if ((int)mn2[e.first].size() == 2 && D[e.first] > mn2[e.first].back()) {
                D[e.first] = mn2[e.first].back();
                pq.push(make_pair(mn2[e.first].back(), e.first));
            }
        }
    }
    return D[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5012 KB Output is correct
2 Correct 3 ms 4988 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 5080 KB Output is correct
5 Correct 3 ms 5012 KB Output is correct
6 Correct 3 ms 5008 KB Output is correct
7 Correct 3 ms 5068 KB Output is correct
8 Correct 3 ms 5068 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5012 KB Output is correct
2 Correct 3 ms 4988 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 5080 KB Output is correct
5 Correct 3 ms 5012 KB Output is correct
6 Correct 3 ms 5008 KB Output is correct
7 Correct 3 ms 5068 KB Output is correct
8 Correct 3 ms 5068 KB Output is correct
9 Correct 5 ms 5196 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 3 ms 5068 KB Output is correct
12 Correct 6 ms 5396 KB Output is correct
13 Correct 6 ms 5452 KB Output is correct
14 Correct 3 ms 5004 KB Output is correct
15 Correct 3 ms 5068 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5012 KB Output is correct
2 Correct 3 ms 4988 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 5080 KB Output is correct
5 Correct 3 ms 5012 KB Output is correct
6 Correct 3 ms 5008 KB Output is correct
7 Correct 3 ms 5068 KB Output is correct
8 Correct 3 ms 5068 KB Output is correct
9 Correct 5 ms 5196 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 3 ms 5068 KB Output is correct
12 Correct 6 ms 5396 KB Output is correct
13 Correct 6 ms 5452 KB Output is correct
14 Correct 3 ms 5004 KB Output is correct
15 Correct 3 ms 5068 KB Output is correct
16 Correct 463 ms 59508 KB Output is correct
17 Correct 84 ms 18704 KB Output is correct
18 Correct 116 ms 19812 KB Output is correct
19 Correct 619 ms 63328 KB Output is correct
20 Correct 296 ms 51880 KB Output is correct
21 Correct 41 ms 10856 KB Output is correct
22 Correct 310 ms 49072 KB Output is correct