Submission #1287006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287006		MinhKien	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	298 ms	48960 KiB

crocodile

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define ii pair <int, int>
#define i3 pair <ii, int>
#define fi first
#define se second

const int N = 1e5 + 10;
// const int M = 1e6 + 10;
const int INF = 2e9;

// int n, m, r[M][2], l[M], k, p[N];
ii dis[N];
vector <ii> v[N];
priority_queue < i3, vector <i3>, greater <i3> > q;

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

    for (int i = 0; i < N; ++i) {
        dis[i] = ii(INF, INF);
    }

    for (int i = 0; i < K; ++i) {
        dis[P[i]] = ii(0, 0);
        q.push(i3(ii(0, 0), P[i]));
    }

    while (!q.empty()) {
        i3 p = q.top(); q.pop();
        int u = p.se, fir = p.fi.fi, sec = p.fi.se;

        if (ii(fir, sec) != dis[u]) continue;

        for (ii z: v[u]) {
            int nxt = z.fi + fir;

            if (nxt < dis[z.se].se) {
                dis[z.se].fi = dis[z.se].se;
                dis[z.se].se = nxt;
                q.push(i3(dis[z.se], z.se));
            } else {
                if (nxt < dis[z.se].fi) {
                    dis[z.se].fi = nxt;
                    q.push(i3(dis[z.se], z.se));
                }
            }
        }
    }

    return dis[0].first;
}

// int main() {
//     freopen("input.txt", "r", stdin);

//     cin.tie(0); cout.tie(0);
//     ios_base::sync_with_stdio(false);

//     cin >> n >> m;
//     for (int i = 1; i <= m; ++i) {
//         cin >> r[i][0] >> r[i][1];
//     }

//     for (int i = 1; i <= m; ++i) cin >> l[i];

//     cin >> k;
//     for (int i = 1; i <= k; ++i) cin >> p[i];

//     cout << travel_plan(n, m, r, l, k, p);

//     return 0;
// }

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