oj.uz

Submission #421202

# Submission time Handle Problem Language Result Execution time Memory
421202 2021-06-08T21:01:49 Z OttoTheDino Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 2000 ms 147888 KB 
#include <bits/stdc++.h>
using namespace std;

#define rep(i,s,e)                      for (ll i = s; i <= e; ++i)
#define rrep(i,s,e)                     for (ll i = s; i >= e; --i)
#define pb                              push_back
#define pf                              push_front
#define fi                              first
#define se                              second
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;

int travel_plan (int n, int m, int r[][2], int l[], int k, int p[]) {
    vii neibs[n];
    rep (i,0,m-1) {
        neibs[r[i][0]].pb({r[i][1], l[i]});
        neibs[r[i][1]].pb({r[i][0], l[i]});
    }

    multiset<ll> doors[n];
    bool done[n]={};
    ll best[n] = {};
    priority_queue<ii, vii, greater<ii>> pq;

    rep (i,0,k-1) pq.push({0, p[i]});

    while (!pq.empty()) {
        ll dist = pq.top().fi, u = pq.top().se;
        pq.pop();

        if (done[u]) continue;
        if (u==0) return dist;

        for (ii vd : neibs[u]) {
            ll v = vd.fi, d = vd.se;
            doors[v].insert(d+dist);
            ll boi = *(++doors[v].begin());
            if ((ll)doors[v].size()>1 && !done[v] && (!best[v] || boi<best[v])) {
                pq.push({boi, v});
                best[v] = boi;
            }
        }

        done[u]=1;
    }

    assert(0==1);
    return -1;
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 3 ms 844 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 9 ms 1888 KB Output is correct
13 Correct 4 ms 972 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 3 ms 588 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 3 ms 844 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 9 ms 1888 KB Output is correct
13 Correct 4 ms 972 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 3 ms 588 KB Output is correct
16 Execution timed out 2082 ms 147888 KB Time limit exceeded
17 Halted 0 ms 0 KB -