oj.uz

Submission #630424

# Submission time Handle Problem Language Result Execution time Memory
630424 2022-08-16T10:54:00 Z NintsiChkhaidze Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 506 ms 77596 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define s second
#define pb push_back
#define ll long long
#define f first
 
const int nn = 300005;
vector <pair<int,ll> > v[nn];
pair<ll,ll> dis[nn];
 
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    for (int i = 0; i < M; i++){
        v[R[i][0]].pb({R[i][1],L[i]});
        v[R[i][1]].pb({R[i][0],L[i]});
    }
    for (int i=0;i<N; i++)
        dis[i] = {1e18,1e18};
 
    using T = pair<ll,int>;
    priority_queue <T, vector <T>, greater <T>> pq;
    for (int i = 0; i < K; i++)
        dis[P[i]] = {0LL,0LL},pq.push({0LL,P[i]});
 
    while(pq.size()){
        ll d = pq.top().f;
        int x = pq.top().s;
        pq.pop();
        if (d != dis[x].s) continue;
        for (auto [to,w]: v[x]){
            ll vl = w + d;
            ll old = dis[to].s;
            if (dis[to].f > vl) {
                dis[to].s = dis[to].f;
                dis[to].f = vl;
            }else if (dis[to].s > vl){
                dis[to].s = vl;
            }
            if (dis[to].s < old) pq.push({dis[to].s, to});
        }
    }
    return dis[0].s;
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:31:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |         for (auto [to,w]: v[x]){
      |                   ^

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 5 ms 7452 KB Output is correct
7 Correct 12 ms 7380 KB Output is correct
8 Correct 5 ms 7380 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 5 ms 7452 KB Output is correct
7 Correct 12 ms 7380 KB Output is correct
8 Correct 5 ms 7380 KB Output is correct
9 Correct 5 ms 7636 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7508 KB Output is correct
12 Correct 6 ms 7892 KB Output is correct
13 Correct 6 ms 8020 KB Output is correct
14 Correct 4 ms 7380 KB Output is correct
15 Correct 4 ms 7508 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 5 ms 7452 KB Output is correct
7 Correct 12 ms 7380 KB Output is correct
8 Correct 5 ms 7380 KB Output is correct
9 Correct 5 ms 7636 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7508 KB Output is correct
12 Correct 6 ms 7892 KB Output is correct
13 Correct 6 ms 8020 KB Output is correct
14 Correct 4 ms 7380 KB Output is correct
15 Correct 4 ms 7508 KB Output is correct
16 Correct 410 ms 71508 KB Output is correct
17 Correct 78 ms 19068 KB Output is correct
18 Correct 91 ms 21308 KB Output is correct
19 Correct 506 ms 77596 KB Output is correct
20 Correct 276 ms 59672 KB Output is correct
21 Correct 37 ms 12916 KB Output is correct
22 Correct 276 ms 54648 KB Output is correct