Submission #361141

#	Time	Username	Problem	Language	Result	Execution time	Memory
361141		Aldas25	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	662 ms	50020 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef vector<pii> vii;

const int MAXN = 100100;

int n, m;
vii adj[MAXN];
vi exits;

ll d1[MAXN], d2[MAXN];
bool vis[MAXN];

void addD (int v, ll d) {
    if (d1[v] == -1) {
        d1[v] = d;
        return;
    }
    if (d2[v] == -1) {
        if (d > d1[v])
            d2[v] = d;
        else {
            d2[v] = d1[v];
            d1[v] = d;
        }
        return;
    }
    if (d >= d2[v]) return;
    d2[v] = d;
    if (d2[v] < d1[v]) swap(d1[v], d2[v]);
}

void dijkstra () {
    FOR(i, 0, n-1) d1[i] = d2[i] = -1;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
    for (int v : exits) {
        d1[v] = d2[v] = 0;
        q.push({d2[v], v});
    }

    while (!q.empty()) {
        int v = q.top().s;
        q.pop();
        if (!vis[v]) {
              //  cout << " v = " << v << endl;
            vis[v] = true;
            for (auto e : adj[v]) {
                int u = e.f;
                ll w = e.s;
                ll was = d2[u];
                addD(u, d2[v] + w);
            //cout << "   u = " << u << " was = " << was << " now =" << d2[u] << " d2+w = " << d2[v]+w << endl;
                if (was != d2[u]) {
                    q.push({d2[u], u});
                }
            }
        }
    }
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    n = N;
    m = M;
    FOR(i, 0, m-1) {
        int u = R[i][0];
        int v = R[i][1];
        int w = L[i];
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    FOR(i, 0, K-1)
        exits.pb(P[i]);

    dijkstra();

    return d2[0];
}

/*

input 1
5 4 3
0 1 2
0 2 3
3 2 1
2 4 4
1 3 4
7

input 2
5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
1 3
14



*/

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