Submission #689696

#	Time	Username	Problem	Language	Result	Execution time	Memory
689696		zeroesandones	악어의 지하 도시 (IOI11_crocodile)	C++17	100 / 100	525 ms	93672 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;

using ll = long long;
using vi = vector<ll>;
using pi = pair<ll, ll>;

#define fr first
#define sc second
#define pb emplace_back

const int mxN = 1e5 + 5;
vector<pi> adj[mxN];
const ll inf = 1e15;

// work backwards maybe?
// start from the exit nodes
// dp[i] = 2nd max of all the nodes we can come from

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    for(int i = 0; i < M; ++i) {
        adj[R[i][0]].pb(R[i][1], L[i]);
        adj[R[i][1]].pb(R[i][0], L[i]);
    }

    priority_queue<pi> pq;
    ll dist[N][2] = {};
    bool vis[N] = {};

    for(int i = 0; i < N; ++i) {
        dist[i][1] = dist[i][0] = inf;
    }

    for(int i = 0; i < K; ++i) {
        dist[P[i]][1] = dist[P[i]][0] = 0;
        pq.emplace(0, P[i]);
    }

    while(!pq.empty()) {
        ll x = pq.top().sc;
        pq.pop();

        if(vis[x]) continue;
        vis[x] = true;

        for(auto [y, w] : adj[x]) {
            ll curr = dist[x][1] + w;
            if(dist[y][0] >= curr) {
                dist[y][1] = dist[y][0];
                dist[y][0] = curr;
                pq.emplace(-dist[y][1], y);
            } else if(dist[y][1] > curr) {
                dist[y][1] = curr;
                pq.emplace(-dist[y][1], y);
            }
        }
    }

    return dist[0][1];
}

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