oj.uz

Submission #497256

# Submission time Handle Problem Language Result Execution time Memory
497256 2021-12-22T21:25:29 Z Leo121 Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1218 ms 101072 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, ll> pii;
struct ura{
    int inicio, destino;
    ll peso;
    const bool operator < (const ura & a) const {
        return peso > a.peso;
    }
};
priority_queue<ura> pq;
bool salidas[100002];
bool primer_camino[100002];
ll respuesta[100002];
vector<pii> graph[100002];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    forn(i, 0, N - 1){
        salidas[i] = 0;
        primer_camino[i] = 0;
        respuesta[i] = 0LL;
    }
    forn(i, 0, M - 1){
        graph[R[i][0]].pb(mp(R[i][1], (ll) L[i]));
        graph[R[i][1]].pb(mp(R[i][0], (ll) L[i]));
    }
    forn(i, 0, K - 1){
        primer_camino[P[i]] = 1;
        salidas[P[i]] = 1;
        for(pii u : graph[P[i]]){
            pq.push({P[i], u.fi, u.se});
        }
    }
    while(!pq.empty()){
        ura act = pq.top();
        pq.pop();
        if(salidas[act.destino]){
            continue;
        }
        if(!primer_camino[act.destino]){
            primer_camino[act.destino] = 1;
            continue;
        }
        salidas[act.destino] = 1;
        respuesta[act.destino] = act.peso;
        for(pii u : graph[act.destino]){
            pq.push({act.destino, u.fi, act.peso + u.se});
        }
    }
    return (int) respuesta[0];

}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 4 ms 3404 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 3 ms 2892 KB Output is correct
12 Correct 8 ms 3920 KB Output is correct
13 Correct 6 ms 4052 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2764 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 4 ms 3404 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 3 ms 2892 KB Output is correct
12 Correct 8 ms 3920 KB Output is correct
13 Correct 6 ms 4052 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2764 KB Output is correct
16 Correct 1142 ms 97548 KB Output is correct
17 Correct 75 ms 13792 KB Output is correct
18 Correct 100 ms 16108 KB Output is correct
19 Correct 1218 ms 101072 KB Output is correct
20 Correct 674 ms 88016 KB Output is correct
21 Correct 38 ms 8132 KB Output is correct
22 Correct 492 ms 50772 KB Output is correct