oj.uz

Submission #787124

# Submission time Handle Problem Language Result Execution time Memory
787124 2023-07-18T20:50:29 Z Sam_a17 Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 440 ms 123032 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;
 
#define ff first
#define ss second
 
ll ttt;
const ll INF=1e16;
const ll MOD=1e9+7;
const ll N=2000007;
ll n,m,k;
vector<pair<ll,ll>>g[N];
 
int travel_plan(int NN, int MM, int R[][2], int L[], int KK, int P[]){
    n=NN;
    m=MM;
    k=KK;
    for(ll i=0;i<m;i++){
        // cout<<R[i][0]<<" "<<R[i][1]<<endl;
        g[R[i][0]].push_back(make_pair(R[i][1],L[i]));
        g[R[i][1]].push_back(make_pair(R[i][0],L[i]));
    }
    priority_queue<pii,vector<pii>,greater<pii>>q;
    vector<ll>mn(n+1,INF),smn(n+1,INF);
    // cout<<mn[0]<<" "<<smn[0]<<endl;
    for(ll i=0;i<k;i++){
        q.push(make_pair(0,P[i]));
        mn[P[i]]=smn[P[i]]=0;
    }
    while(!q.empty()){
        ll v=q.top().ss;
        ll w=q.top().ff;
        // cout<<v<<" "<<w<<endl;
        // cout<<mn[v]<<" "<<smn[v]<<endl<<endl;
        q.pop();
        if(smn[v]==w){
            for(pii x:g[v]){
                ll to=x.ff;
                ll dist=x.ss;
                // cout<<v<<" "<<to<<" "<<dist<<endl;
                // cout<<mn[to]<<" "<<smn[v]<<endl;
                // cout<<endl;
                if(mn[to]>smn[v]+dist){
                    smn[to]=mn[to];
                    mn[to]=smn[v]+dist;
                    q.push(make_pair(smn[to],to));
                }
                else if(smn[to]>smn[v]+dist){
                    smn[to]=smn[v]+dist;
                    q.push(make_pair(smn[to],to));
                }
            }
        }
    }
    return smn[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47260 KB Output is correct
2 Correct 19 ms 47276 KB Output is correct
3 Correct 25 ms 47200 KB Output is correct
4 Correct 25 ms 47380 KB Output is correct
5 Correct 25 ms 47420 KB Output is correct
6 Correct 22 ms 47340 KB Output is correct
7 Correct 20 ms 47316 KB Output is correct
8 Correct 22 ms 47296 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47260 KB Output is correct
2 Correct 19 ms 47276 KB Output is correct
3 Correct 25 ms 47200 KB Output is correct
4 Correct 25 ms 47380 KB Output is correct
5 Correct 25 ms 47420 KB Output is correct
6 Correct 22 ms 47340 KB Output is correct
7 Correct 20 ms 47316 KB Output is correct
8 Correct 22 ms 47296 KB Output is correct
9 Correct 22 ms 47716 KB Output is correct
10 Correct 23 ms 47268 KB Output is correct
11 Correct 22 ms 47468 KB Output is correct
12 Correct 28 ms 47932 KB Output is correct
13 Correct 22 ms 48040 KB Output is correct
14 Correct 21 ms 47296 KB Output is correct
15 Correct 21 ms 47360 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47260 KB Output is correct
2 Correct 19 ms 47276 KB Output is correct
3 Correct 25 ms 47200 KB Output is correct
4 Correct 25 ms 47380 KB Output is correct
5 Correct 25 ms 47420 KB Output is correct
6 Correct 22 ms 47340 KB Output is correct
7 Correct 20 ms 47316 KB Output is correct
8 Correct 22 ms 47296 KB Output is correct
9 Correct 22 ms 47716 KB Output is correct
10 Correct 23 ms 47268 KB Output is correct
11 Correct 22 ms 47468 KB Output is correct
12 Correct 28 ms 47932 KB Output is correct
13 Correct 22 ms 48040 KB Output is correct
14 Correct 21 ms 47296 KB Output is correct
15 Correct 21 ms 47360 KB Output is correct
16 Correct 359 ms 114896 KB Output is correct
17 Correct 102 ms 62592 KB Output is correct
18 Correct 110 ms 64884 KB Output is correct
19 Correct 440 ms 123032 KB Output is correct
20 Correct 283 ms 101072 KB Output is correct
21 Correct 61 ms 54968 KB Output is correct
22 Incorrect 271 ms 96408 KB Output isn't correct
23 Halted 0 ms 0 KB -