oj.uz

Submission #737877

# Submission time Handle Problem Language Result Execution time Memory
737877 2023-05-07T21:51:10 Z Skywk Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 977 ms 62884 KB 
#include "crocodile.h"
#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;
vector<pair<int, int>> graph[MAXN+1];
int city[MAXN];
priority_queue<long long> best[MAXN+1];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    for(int i=0; i<M; i++){
        graph[R[i][0]].push_back({R[i][1], L[i]});
        graph[R[i][1]].push_back({R[i][0], L[i]});
    }
    set<pair<long long, int>> pq;
    for(int i=0; i<K; i++){
        best[P[i]].push(0);
        best[P[i]].push(0);
        pq.insert({0, P[i]});
    }
    while(!pq.empty()){
        auto [d, v] = *pq.begin();
        pq.erase(pq.begin());
        if(best[v].size() < 2 || d != best[v].top()) continue;
        for(auto [u, c] : graph[v]){
            best[u].push(d + c);
            if(best[u].size() > 2){
                if(best[u].top() == d + c){
                    best[u].pop();
                    continue;
                }
                pq.erase({u, best[u].top()});
                best[u].pop();
            }
            pq.insert({d + c, u});
        }
    }
    return best[0].top();
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 4 ms 5844 KB Output is correct
4 Correct 4 ms 5972 KB Output is correct
5 Correct 4 ms 5936 KB Output is correct
6 Correct 3 ms 5844 KB Output is correct
7 Correct 4 ms 5972 KB Output is correct
8 Correct 4 ms 5972 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 4 ms 5844 KB Output is correct
4 Correct 4 ms 5972 KB Output is correct
5 Correct 4 ms 5936 KB Output is correct
6 Correct 3 ms 5844 KB Output is correct
7 Correct 4 ms 5972 KB Output is correct
8 Correct 4 ms 5972 KB Output is correct
9 Correct 5 ms 6100 KB Output is correct
10 Correct 3 ms 5844 KB Output is correct
11 Correct 4 ms 5932 KB Output is correct
12 Correct 7 ms 6228 KB Output is correct
13 Correct 6 ms 6228 KB Output is correct
14 Correct 3 ms 5844 KB Output is correct
15 Correct 4 ms 5844 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 4 ms 5844 KB Output is correct
4 Correct 4 ms 5972 KB Output is correct
5 Correct 4 ms 5936 KB Output is correct
6 Correct 3 ms 5844 KB Output is correct
7 Correct 4 ms 5972 KB Output is correct
8 Correct 4 ms 5972 KB Output is correct
9 Correct 5 ms 6100 KB Output is correct
10 Correct 3 ms 5844 KB Output is correct
11 Correct 4 ms 5932 KB Output is correct
12 Correct 7 ms 6228 KB Output is correct
13 Correct 6 ms 6228 KB Output is correct
14 Correct 3 ms 5844 KB Output is correct
15 Correct 4 ms 5844 KB Output is correct
16 Correct 628 ms 53076 KB Output is correct
17 Correct 89 ms 19512 KB Output is correct
18 Correct 127 ms 20244 KB Output is correct
19 Correct 977 ms 62884 KB Output is correct
20 Correct 263 ms 41652 KB Output is correct
21 Correct 46 ms 11940 KB Output is correct
22 Correct 304 ms 38112 KB Output is correct