oj.uz

Submission #342809

# Submission time Handle Problem Language Result Execution time Memory
342809 2021-01-02T21:33:37 Z ThinGarfield Crocodile's Underground City (IOI11_crocodile) C++11
0 / 100
 3 ms 3692 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;  // (-mindist, -secdist, 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(-mindist[nbrvtx], -secdist[vtx]), nbrvtx));
            } else if (x < secdist[nbrvtx]) {
                secdist[nbrvtx] = x;
                q.emplace(make_pair(make_pair(-mindist[nbrvtx], -secdist[vtx]), nbrvtx));
            }
        }
    }

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

    return secdist[0];
}

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3692 KB Output is correct
2 Incorrect 3 ms 3692 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3692 KB Output is correct
2 Incorrect 3 ms 3692 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3692 KB Output is correct
2 Incorrect 3 ms 3692 KB Output isn't correct
3 Halted 0 ms 0 KB -