oj.uz

Submission #985323

# Submission time Handle Problem Language Result Execution time Memory
985323 2024-05-17T15:14:10 Z doducanh Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 409 ms 91724 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) x.begin(),x.end();
using ll=long long;
const ll INF=1LL<<60;
using pll=pair<ll,ll>;
 
inline void srt(array<ll,3> &arr){
    arr[1]=min(arr[1],arr[2]);
    if(arr[0]>arr[1]){
        swap(arr[0],arr[1]);
    }
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    vector<array<ll,3>> order(N,{INF,INF,INF});
    priority_queue<pll,vector<pll>,greater<pll>> vert;
    vector<ll> dist(N,INF);
    rep(i,K){
        dist[P[i]]=0;
        order[P[i]]={0,0,0};
        vert.push(pll(0,P[i]));
    }
    vector<vector<pll>> gr(N);
    rep(i,M){
        gr[R[i][0]].emplace_back(pll(R[i][1],L[i]));
        gr[R[i][1]].emplace_back(pll(R[i][0],L[i]));
    }
    while(!vert.empty()){
        int pos;
        ll dis;
        tie(dis,pos)=vert.top();
        vert.pop();
        if(dist[pos]!=dis)continue;
        for(auto &[t,l]:gr[pos]){
            order[t][2]=dis+l;
            srt(order[t]);
            if(dist[t]>order[t][1]){
                dist[t]=order[t][1];
                vert.push(pll(dist[t],t));
            }
        }
    }
    return dist[0];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:36:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |         for(auto &[t,l]:gr[pos]){
      |                   ^

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4544 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 3 ms 5064 KB Output is correct
13 Correct 3 ms 5212 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4544 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 3 ms 5064 KB Output is correct
13 Correct 3 ms 5212 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 337 ms 82880 KB Output is correct
17 Correct 53 ms 21072 KB Output is correct
18 Correct 70 ms 23376 KB Output is correct
19 Correct 409 ms 91724 KB Output is correct
20 Correct 214 ms 66132 KB Output is correct
21 Correct 27 ms 11600 KB Output is correct
22 Correct 260 ms 64860 KB Output is correct