Submission #910997

#	Time	Username	Problem	Language	Result	Execution time	Memory
910997		Ghetto	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	956 ms	125096 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pil = pair<int, lint>;
using pli = pair<lint, int>;
static const int MAX_N = 1e5 + 5;

// Check program not run multiple times
static int n, m;
static vector<pil> adj[MAX_N];
static int k;
static bool is_exit[MAX_N];

static int seen[MAX_N];
static lint dist[MAX_N];
static priority_queue<pli, vector<pli>, greater<pli>> order;
lint dijk() {
    for (int i = 0; i < n; i++) {
        if (!is_exit[i]) continue;
        seen[i] = 1;
        order.push({0, i});
    }

    while (order.size()) {
        int u = order.top().second;
        lint d = order.top().first;
        order.pop();

        if (seen[u] == 0) {
            seen[u] = 1;
            continue;
        } else if (seen[u] == 1) {
            seen[u] = 2;
            dist[u] = d;
        } else continue;

        for (pil e : adj[u]) {
            lint new_dist = e.second + dist[u];
            order.push({new_dist, e.first});
        }
    }

    return dist[0];
}

int travel_plan(int tmp_n, int tmp_m, int tmp_r[][2], int tmp_l[], int tmp_k, int tmp_p[]) {
    n = tmp_n;
    m = tmp_m;
    for (int i = 0; i < m; i++) {
        int u = tmp_r[i][0], v = tmp_r[i][1];
        lint w = tmp_l[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    k = tmp_k;
    for (int i = 0; i < k; i++)
        is_exit[tmp_p[i]] = true;
    
    lint ans = dijk();
    return ans;
}

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11