oj.uz

Submission #1041782

# Submission time Handle Problem Language Result Execution time Memory
1041782 2024-08-02T08:17:44 Z khanhtb Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 243 ms 74152 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define pf push_front
#define vi vector<ll>
#define vii vector<vi>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define all(a) a.begin(), a.end()
#define fi first
#define se second
using namespace std;
const ll mod = 1e9+7; 
const ll inf = 1e18;
const ll blocksz = 320;
const ll N = 3e5+8;
pair<int,int> d[N];
int n,m,k;
vector<pair<int,int>> g[N];
vector<int> s;
bool use[N];
void dijkstra(vector<int> &s){
    for(int i = 0; i < n; i++) d[i] = {mod,mod};
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    for(int x:s){
        pq.push({0,x});
        d[x].fi = d[x].se = 0;
    }
    while(pq.size()){
        int du = pq.top().fi, u = pq.top().se;
        pq.pop();
        if(use[u]) continue;
        use[u] = 1;
        for(pair<int,int> ed:g[u]){
            int v = ed.fi, w = ed.se;
            if(du + w < d[v].fi){
                d[v].se = d[v].fi;
                d[v].fi = du + w;
                pq.push({d[v].se,v});
            }
            else if(du + w < d[v].se){
                d[v].se = du + w;
                pq.push({d[v].se,v});
            }
        }
    }
}
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 < m; i++){
        int u = R[i][0], v = R[i][1], w = L[i];
        g[u].pb({v,w});
        g[v].pb({u,w});
    }
    for(int i = 0; i < k; i++){
        int x = P[i];
        s.pb(x);
    }
    dijkstra(s);
    return d[0].se;
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12748 KB Output is correct
3 Correct 1 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 3 ms 12636 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 3 ms 13148 KB Output is correct
14 Correct 2 ms 12636 KB Output is correct
15 Correct 2 ms 12636 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12748 KB Output is correct
3 Correct 1 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 3 ms 12636 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 3 ms 13148 KB Output is correct
14 Correct 2 ms 12636 KB Output is correct
15 Correct 2 ms 12636 KB Output is correct
16 Correct 208 ms 68360 KB Output is correct
17 Correct 47 ms 25804 KB Output is correct
18 Correct 60 ms 27328 KB Output is correct
19 Correct 243 ms 74152 KB Output is correct
20 Correct 145 ms 60244 KB Output is correct
21 Correct 22 ms 18864 KB Output is correct
22 Correct 169 ms 57936 KB Output is correct