oj.uz

Submission #466718

# Submission time Handle Problem Language Result Execution time Memory
466718 2021-08-20T13:54:09 Z FEDIKUS Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 542 ms 58980 KB 
#include "crocodile.h"

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define xx first
#define yy second

using namespace std;

typedef pair<int,int> pii;

const int maxn=1e5+10;

vector<pii> g[maxn];
pii cene[maxn];

void uradi(pii &a,int b){
    if(b<a.xx){
        a.yy=a.xx;
        a.xx=b;
    }else if(b<a.yy){
        a.yy=b;
    }
}

int kurc(int k,int* p){
    priority_queue<pii,vector<pii>,greater<pii> > pq;
    for(int i=0;i<maxn;i++) cene[i]={INT_MAX,INT_MAX};
    for(int i=0;i<k;i++){
        pq.push(mp(0,p[i]));
        cene[p[i]]={0,0};
    }
    while(!pq.empty()){
        pii vrh=pq.top();
        pq.pop();
        if(vrh.xx!=cene[vrh.yy].yy) continue;
        if(vrh.yy==0) return vrh.xx;
        for(pii i:g[vrh.yy]){
            int sc=cene[i.xx].yy;
            uradi(cene[i.xx],vrh.xx+i.yy);
            if(sc>cene[i.xx].yy){
                pq.push(mp(cene[i.xx].yy,i.xx));
            }
        }
    }
    return -1;
}

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){
    for(int i=0;i<m;i++){
        g[r[i][0]].pb(mp(r[i][1],l[i]));
        g[r[i][1]].pb(mp(r[i][0],l[i]));
    }
    return kurc(k,p);
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct
3 Correct 2 ms 3404 KB Output is correct
4 Correct 3 ms 3532 KB Output is correct
5 Correct 3 ms 3404 KB Output is correct
6 Correct 2 ms 3404 KB Output is correct
7 Correct 3 ms 3404 KB Output is correct
8 Correct 3 ms 3404 KB Output is correct
9 Correct 4 ms 3696 KB Output is correct
10 Correct 2 ms 3424 KB Output is correct
11 Correct 3 ms 3564 KB Output is correct
12 Correct 6 ms 3824 KB Output is correct
13 Correct 5 ms 3916 KB Output is correct
14 Correct 3 ms 3424 KB Output is correct
15 Correct 3 ms 3532 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct
3 Correct 2 ms 3404 KB Output is correct
4 Correct 3 ms 3532 KB Output is correct
5 Correct 3 ms 3404 KB Output is correct
6 Correct 2 ms 3404 KB Output is correct
7 Correct 3 ms 3404 KB Output is correct
8 Correct 3 ms 3404 KB Output is correct
9 Correct 4 ms 3696 KB Output is correct
10 Correct 2 ms 3424 KB Output is correct
11 Correct 3 ms 3564 KB Output is correct
12 Correct 6 ms 3824 KB Output is correct
13 Correct 5 ms 3916 KB Output is correct
14 Correct 3 ms 3424 KB Output is correct
15 Correct 3 ms 3532 KB Output is correct
16 Correct 456 ms 55828 KB Output is correct
17 Correct 81 ms 13680 KB Output is correct
18 Correct 92 ms 15112 KB Output is correct
19 Correct 542 ms 58980 KB Output is correct
20 Correct 325 ms 50268 KB Output is correct
21 Correct 42 ms 8092 KB Output is correct
22 Correct 361 ms 46452 KB Output is correct