Submission #951014

#	Time	Username	Problem	Language	Result	Execution time	Memory
951014		efishel	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	819 ms	123048 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;

const ll MAXN = 1E5+16;
vector <pair <ll, ll> > adj[MAXN];

int travel_plan (int _n, int _m, int _r[][2], int _l[], int _k, int _p[]) {
    ll n = _n, m = _m, k = _k;
    for (ll i = 0; i < m; i++) {
        ll u = _r[i][0], v = _r[i][1];
        ll w = _l[i];
        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
    }
    priority_queue <pair <ll, ll> > pq;
    vll cvis(n, 0);
    vector <bool> vis(n, false);
    vll dis(n);
    vll srcs(_p, _p+k);
    for (ll u : srcs) {
        cvis[u] = 1;
        dis[u] = 0;
        pq.push({ -dis[u], u });
    }
    while (pq.size()) {
        auto [disU, u] = pq.top(); disU = -disU; pq.pop();
        cvis[u]++;
        if (cvis[u] != 2) continue;
        dis[u] = disU;
        for (auto [v, w] : adj[u]) {
            pq.push({ -(dis[u]+w), v });
        }
    }
    return int(dis[0]);
}

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