Submission #753174

#	Time	Username	Problem	Language	Result	Execution time	Memory
753174		PanosPask	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	537 ms	63072 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, int> pli;

const ll INF = 1e17;

vector<vector<ll>> plan;
vector<vector<pi>> adj_list;
vector<bool> visited;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    adj_list.resize(N);

    for (int i = 0; i < M; i++) {
        adj_list[R[i][0]].pb(mp(R[i][1], L[i]));
        adj_list[R[i][1]].pb(mp(R[i][0], L[i]));
    }

    plan.assign(N, vector<ll>(2, INF));
    visited.assign(N, false);

    priority_queue<pi, vector<pi>, greater<pi>> q;

    for (int i = 0; i < K; i++) {
        plan[P[i]][0] = plan[P[i]][1] = 0;
        q.push(mp(0, P[i]));
    }

    while (!q.empty()) {
        int v = q.top().s;
        q.pop();

        if (visited[v])
            continue;
        visited[v] = true;

        for (auto u : adj_list[v]) {
            ll curd = plan[v][1] + u.s;

            if (plan[u.f][0] > curd) {
                plan[u.f][1] = plan[u.f][0];
                plan[u.f][0] = curd;

                if (plan[u.f][1] != INF)
                    q.push(mp(plan[u.f][1], u.f));
            }
            else if (plan[u.f][1] > curd) {
                plan[u.f][1] = curd;

                q.push(mp(plan[u.f][1], u.f));
            }
        }
    }

    return plan[0][1];
}

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