oj.uz

Submission #137016

# Submission time Handle Problem Language Result Execution time Memory
137016 2019-07-26T22:31:31 Z MladenP Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 904 ms 67364 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
#define MAXN 100010
#define STIZE(x) fprintf(stderr, "STIZE%d\n", x);
#define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x);
#define NL(x) printf("%c", " \n"[(x)]);
#define lld long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define mid (l+r)/2
#define endl '\n'
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 1000000000000000LL
#define INF 1000000000
#define EPS 1e-9
using namespace std;
priority_queue<pii, vector<pii>, greater<pii> > pq;
int dist[MAXN], pos[MAXN];
vector<pii> adj[MAXN];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    for(int i = 0; i < N; i++) dist[i] = pos[i] = -1;
    for(int i = 0; i < K; i++) {
        pq.push({0, P[i]});
        pq.push({0, P[i]});
    }
    for(int i = 0; i < M; i++) {
        adj[R[i][0]].pb({R[i][1], L[i]});
        adj[R[i][1]].pb({R[i][0], L[i]});
    }
    while(!pq.empty()) {
        pii vrh = pq.top(); pq.pop();
        if(dist[vrh.se] != -1 && pos[vrh.se] != -1) continue;
        else if(pos[vrh.se] == -1) {
            pos[vrh.se] = vrh.fi;
        } else {
            dist[vrh.se] = vrh.fi;
            for(auto x : adj[vrh.se]) {
                if(dist[x.fi] == -1) {
                    pq.push({vrh.fi+x.se, x.fi});
                }
            }
        }
    }
    return dist[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2812 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 7 ms 3068 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 5 ms 2936 KB Output is correct
12 Correct 9 ms 3320 KB Output is correct
13 Correct 9 ms 3448 KB Output is correct
14 Correct 4 ms 2684 KB Output is correct
15 Correct 5 ms 2812 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2812 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 7 ms 3068 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 5 ms 2936 KB Output is correct
12 Correct 9 ms 3320 KB Output is correct
13 Correct 9 ms 3448 KB Output is correct
14 Correct 4 ms 2684 KB Output is correct
15 Correct 5 ms 2812 KB Output is correct
16 Correct 833 ms 64336 KB Output is correct
17 Correct 103 ms 13924 KB Output is correct
18 Correct 148 ms 15096 KB Output is correct
19 Correct 904 ms 67364 KB Output is correct
20 Correct 556 ms 57672 KB Output is correct
21 Correct 52 ms 7672 KB Output is correct
22 Correct 517 ms 46400 KB Output is correct