Submission #72704

#	Time	Username	Problem	Language	Result	Execution time	Memory
72704		chpipis	Crocodile's Underground City (IOI11_crocodile)	C++11	100 / 100	1296 ms	59676 KiB

crocodile

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

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef long long ll;

const int MAXN = 1e5 + 5;

vii gr[MAXN];
ll dist[MAXN];
bool visit[MAXN];
ll mn[MAXN];

const ll INF = 1e15;

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

    priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
    fill(dist, dist + MAXN, INF);
    memset(visit, false, sizeof visit);

    for (int i = 0; i < K; i++) {
        visit[P[i]] = true;
        pq.push(mp(0, P[i]));
    }

    while (!pq.empty()) {
        ll w = pq.top().fi;
        int u = pq.top().se;
        pq.pop();

        if (visit[u]) {
            if (dist[u] == INF) {
                dist[u] = w;
            } else {
                continue;
            }
        } else {
            visit[u] = true;
            continue;
        }

        for (auto v : gr[u]) {
            if (dist[v.fi] == INF) {
                pq.push(mp(w + v.se, v.fi));
            }
        }
    }

    return dist[0];
    /*
    fill(mn, mn + MAXN, INF);

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

    while (!pq.empty()) {
        ll w = pq.top().fi;
        int u = pq.top().se;
        pq.pop();

        if (dist[u] < w) continue;

        for (auto v : gr[u]) {
            ll cost = w + ( ll )v.se;
            if (cost < mn[v.fi] || cost < dist[v.fi]) {
                if (cost < mn[v.fi]) {
                    dist[v.fi] = mn[v.fi];
                    mn[v.fi] = cost;
                } else if (cost < dist[v.fi]) {
                    dist[v.fi] = cost;
                }
                if (dist[v.fi] < INF)
                    pq.push(mp(dist[v.fi], v.fi));
            }
        }
    }

    assert(dist[0] < INF);

    return (int)dist[0];
    */
}

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