oj.uz

Submission #445175

# Submission time Handle Problem Language Result Execution time Memory
445175 2021-07-16T18:20:48 Z JovanB Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 996 ms 76336 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
ll dist1[100005];
ll dist2[100005];
bool ext[100005];
 
const int MX = 1000000007;
 
int n;
vector <pair <int, ll>> graf[100005];
set <pair <ll, int>> q;
 
void sp(){
 
    for(int i=1; i<=n; i++){
        if(ext[i]) dist2[i] = 0;
        else dist2[i] = MX;
        dist1[i] = dist2[i];
        q.insert({dist2[i], i});
    }
    while(!q.empty()){
        int v = q.begin()->second;
        q.erase(q.begin());
        if(v == 1) return;
        for(auto pr : graf[v]){
            int c = pr.first;
            int dis = pr.second+dist2[v];
            if(dis < dist1[c]){
                q.erase({dist2[c], c});
                dist2[c] = dist1[c];
                dist1[c] = dis;
                q.insert({dist2[c], c});
            }
            else if(dis < dist2[c]){
                q.erase({dist2[c], c});
                dist2[c] = dis;
                q.insert({dist2[c], c});
            }
        }
    }
}
 
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    n = N;
    int m = M;
    int k = K;
    for(int i=0; i<m; i++){
        R[i][0]++;
        R[i][1]++;
        graf[R[i][0]].push_back({R[i][1], L[i]});
        graf[R[i][1]].push_back({R[i][0], L[i]});
    }
    for(int i=0; i<k; i++){
        P[i]++;
        ext[P[i]] = 1;
    }
    sp();
    return dist2[1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 3 ms 2792 KB Output is correct
6 Correct 3 ms 2764 KB Output is correct
7 Correct 3 ms 2724 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 3 ms 2792 KB Output is correct
6 Correct 3 ms 2764 KB Output is correct
7 Correct 3 ms 2724 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 4 ms 2992 KB Output is correct
10 Correct 2 ms 2648 KB Output is correct
11 Correct 3 ms 2840 KB Output is correct
12 Correct 6 ms 3276 KB Output is correct
13 Correct 5 ms 3404 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 3 ms 2764 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 3 ms 2792 KB Output is correct
6 Correct 3 ms 2764 KB Output is correct
7 Correct 3 ms 2724 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 4 ms 2992 KB Output is correct
10 Correct 2 ms 2648 KB Output is correct
11 Correct 3 ms 2840 KB Output is correct
12 Correct 6 ms 3276 KB Output is correct
13 Correct 5 ms 3404 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 3 ms 2764 KB Output is correct
16 Correct 631 ms 71080 KB Output is correct
17 Correct 153 ms 23876 KB Output is correct
18 Correct 163 ms 25476 KB Output is correct
19 Correct 996 ms 76336 KB Output is correct
20 Correct 329 ms 61508 KB Output is correct
21 Correct 68 ms 11632 KB Output is correct
22 Correct 396 ms 58092 KB Output is correct