oj.uz

Submission #342808

# Submission time Handle Problem Language Result Execution time Memory
342808 2021-01-02T21:33:05 Z ThinGarfield Crocodile's Underground City (IOI11_crocodile) C++11
100 / 100
 675 ms 49172 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define f first
#define s second

constexpr int big = 1e9 + 9;
constexpr int maxn = 1e5 + 5;

vector<pii> adj[maxn];  // (vtx, wgt)
bool isexit[maxn];      // true if is exit
int mindist[maxn];      // minimum distance
int secdist[maxn];      // second-minimum distance (the answer)
bool done[maxn];
priority_queue<pair<pii, int>> q;  // (-secdist, -mindist, vtx)

void reset() {
    for (int i = 0; i < maxn; i++) {
        isexit[i] = false;
        mindist[i] = 0;
        secdist[i] = 0;
        done[i] = false;
        adj[i].clear();
    }
    while (!q.empty()) q.pop();  // q should be empty anyways... but still
}

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
    reset();
    // reading input
    for (int i = 0; i < m; i++) {
        int a = r[i][0], b = r[i][1], c = l[i];
        adj[a].push_back(make_pair(b, c));
        adj[b].push_back(make_pair(a, c));
    }
    for (int i = 0; i < k; i++) {
        isexit[p[i]] = true;
    }

    // setting up djikstra's things
    for (int i = 0; i < n; i++) {
        if (isexit[i]) {
            mindist[i] = 0;
            secdist[i] = 0;
            q.emplace(make_pair(make_pair(0, 0), i));
        } else {
            mindist[i] = big;
            secdist[i] = big;
        }
    }

    while (!q.empty()) {
        int vtx = q.top().s;
        q.pop();
        if (done[vtx]) continue;
        done[vtx] = true;
        for (pii nbr : adj[vtx]) {
            int nbrvtx = nbr.f;
            int wgt = nbr.s;
            int x = wgt + secdist[vtx];
            if (x < mindist[nbrvtx]) {
                secdist[nbrvtx] = mindist[nbrvtx];
                mindist[nbrvtx] = x;
                q.emplace(make_pair(make_pair(-secdist[nbrvtx], -mindist[vtx]), nbrvtx));
            } else if (x < secdist[nbrvtx]) {
                secdist[nbrvtx] = x;
                q.emplace(make_pair(make_pair(-secdist[nbrvtx], -mindist[vtx]), nbrvtx));
            }
        }
    }

    // for (int i = 0; i < n; i++) {
    //     cout << "node " << i << " : " << mindist[i] << ", " << secdist[i] << '\n';
    // }

    return secdist[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3692 KB Output is correct
2 Correct 3 ms 3692 KB Output is correct
3 Correct 4 ms 3840 KB Output is correct
4 Correct 3 ms 3692 KB Output is correct
5 Correct 3 ms 3692 KB Output is correct
6 Correct 3 ms 3692 KB Output is correct
7 Correct 3 ms 3692 KB Output is correct
8 Correct 3 ms 3692 KB Output is correct
9 Correct 4 ms 3948 KB Output is correct
10 Correct 3 ms 3692 KB Output is correct
11 Correct 4 ms 3820 KB Output is correct
12 Correct 8 ms 4196 KB Output is correct
13 Correct 6 ms 4076 KB Output is correct
14 Correct 3 ms 3712 KB Output is correct
15 Correct 3 ms 3692 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3692 KB Output is correct
2 Correct 3 ms 3692 KB Output is correct
3 Correct 4 ms 3840 KB Output is correct
4 Correct 3 ms 3692 KB Output is correct
5 Correct 3 ms 3692 KB Output is correct
6 Correct 3 ms 3692 KB Output is correct
7 Correct 3 ms 3692 KB Output is correct
8 Correct 3 ms 3692 KB Output is correct
9 Correct 4 ms 3948 KB Output is correct
10 Correct 3 ms 3692 KB Output is correct
11 Correct 4 ms 3820 KB Output is correct
12 Correct 8 ms 4196 KB Output is correct
13 Correct 6 ms 4076 KB Output is correct
14 Correct 3 ms 3712 KB Output is correct
15 Correct 3 ms 3692 KB Output is correct
16 Correct 505 ms 44000 KB Output is correct
17 Correct 111 ms 12388 KB Output is correct
18 Correct 130 ms 13668 KB Output is correct
19 Correct 675 ms 49172 KB Output is correct
20 Correct 320 ms 37484 KB Output is correct
21 Correct 49 ms 7596 KB Output is correct
22 Correct 376 ms 33108 KB Output is correct