oj.uz

Submission #965399

# Submission time Handle Problem Language Result Execution time Memory
965399 2024-04-18T12:48:45 Z hirayuu_oj Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 400 ms 91452 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];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4640 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 1 ms 4556 KB Output is correct
9 Correct 2 ms 4696 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 4956 KB Output is correct
13 Correct 3 ms 5156 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 4696 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4640 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 1 ms 4556 KB Output is correct
9 Correct 2 ms 4696 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 4956 KB Output is correct
13 Correct 3 ms 5156 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 322 ms 82972 KB Output is correct
17 Correct 58 ms 21072 KB Output is correct
18 Correct 70 ms 23380 KB Output is correct
19 Correct 400 ms 91452 KB Output is correct
20 Correct 210 ms 66032 KB Output is correct
21 Correct 26 ms 11612 KB Output is correct
22 Correct 231 ms 64920 KB Output is correct