oj.uz

Submission #342807

# Submission time Handle Problem Language Result Execution time Memory
342807 2021-01-02T21:32:11 Z ThinGarfield Crocodile's Underground City (IOI11_crocodile) C++11
100 / 100
 645 ms 60380 KB 
#include "crocodile.h"

#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 3 ms 3692 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 3 ms 3692 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 3900 KB Output is correct
10 Correct 3 ms 3692 KB Output is correct
11 Correct 4 ms 3820 KB Output is correct
12 Correct 6 ms 4204 KB Output is correct
13 Correct 6 ms 4204 KB Output is correct
14 Correct 3 ms 3692 KB Output is correct
15 Correct 3 ms 3820 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 3 ms 3692 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 3900 KB Output is correct
10 Correct 3 ms 3692 KB Output is correct
11 Correct 4 ms 3820 KB Output is correct
12 Correct 6 ms 4204 KB Output is correct
13 Correct 6 ms 4204 KB Output is correct
14 Correct 3 ms 3692 KB Output is correct
15 Correct 3 ms 3820 KB Output is correct
16 Correct 505 ms 55136 KB Output is correct
17 Correct 112 ms 15588 KB Output is correct
18 Correct 131 ms 17124 KB Output is correct
19 Correct 645 ms 60380 KB Output is correct
20 Correct 322 ms 48748 KB Output is correct
21 Correct 51 ms 9004 KB Output is correct
22 Correct 354 ms 44316 KB Output is correct