oj.uz

Submission #318743

# Submission time Handle Problem Language Result Execution time Memory
318743 2020-11-03T05:13:02 Z thecodingwizard Crocodile's Underground City (IOI11_crocodile) C++11
100 / 100
 588 ms 61372 KB 
#include <bits/stdc++.h>
#include "crocodile.h"

using namespace std;

#define ii pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define F0R(i, n) for (int i = 0; i < n; i++)
#define inf 1000000010

vector<ii> adj[100000];
int d1[100000], d2[100000];
bool vis[100000];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
    F0R(i, n) d1[i] = d2[i] = inf;
    F0R(i, m) {
        int a = r[i][0], b = r[i][1], L = l[i];
        adj[a].pb(mp(b, L));
        adj[b].pb(mp(a, L));
    }
    priority_queue<ii, vector<ii>, greater<ii>> pq;
    for (int i = 0; i < k; i++) {
        int x = p[i];
        d1[x] = d2[x] = 0;
        pq.push(mp(0, x));
    }
    while (!pq.empty()) {
        ii u = pq.top(); pq.pop();
        if (vis[u.s]) continue;
        vis[u.s] = true;
        for (auto v : adj[u.s]) {
            int d = d2[u.s] + v.s;
            if (d1[v.f] > d) {
                d2[v.f] = d1[v.f];
                d1[v.f] = d;
            } else if (d2[v.f] > d) {
                d2[v.f] = d;
            } else {
                continue;
            }
            if (d2[v.f] != inf) pq.push(mp(d2[v.f], v.f));
        }
    }
    return d2[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2796 KB Output is correct
4 Correct 3 ms 2816 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 2 ms 2796 KB Output is correct
7 Correct 3 ms 2924 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2796 KB Output is correct
4 Correct 3 ms 2816 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 2 ms 2796 KB Output is correct
7 Correct 3 ms 2924 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 4 ms 2924 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct
12 Correct 7 ms 3180 KB Output is correct
13 Correct 6 ms 3180 KB Output is correct
14 Correct 2 ms 2796 KB Output is correct
15 Correct 3 ms 2796 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2796 KB Output is correct
4 Correct 3 ms 2816 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 2 ms 2796 KB Output is correct
7 Correct 3 ms 2924 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 4 ms 2924 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct
12 Correct 7 ms 3180 KB Output is correct
13 Correct 6 ms 3180 KB Output is correct
14 Correct 2 ms 2796 KB Output is correct
15 Correct 3 ms 2796 KB Output is correct
16 Correct 484 ms 57436 KB Output is correct
17 Correct 77 ms 13924 KB Output is correct
18 Correct 102 ms 15464 KB Output is correct
19 Correct 588 ms 61372 KB Output is correct
20 Correct 309 ms 49604 KB Output is correct
21 Correct 38 ms 7780 KB Output is correct
22 Correct 332 ms 46180 KB Output is correct