Submission #1033497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033497		ArthuroWich	Crocodile's Underground City (IOI11_crocodile)	C++17	46 / 100	2 ms	1116 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    long long int n, m;
    n = N;
    m = M;
    vector<long long int> vis(n, 0), bestdist(n, INT64_MAX), seconddist(n, INT64_MAX), proc(n, 0);
    vector<vector<pair<long long int, long long int>>> adj(n+1);
    for (long long int i = 0; i < m; i++) {
        adj[R[i][0]].push_back({R[i][1], L[i]});
        adj[R[i][1]].push_back({R[i][0], L[i]});
    }
    set<pair<long long int, long long int>> pq;
    for (long long int i = 0; i < K; i++) {
        pq.insert({0, P[i]});
    }
    while(!pq.empty()) {
        auto [d, a] = *pq.begin();
        pq.erase(pq.begin());
        d = abs(d);
        for (auto [b, w] : adj[a]) {
            vis[b]++;
            if (vis[b] == 1) {
                bestdist[b] = d+w;
            } else if (vis[b] == 2) {
                long long int v = bestdist[b];
                bestdist[b] = min(v, d+w);
                seconddist[b] = max(v, d+w);
                pq.insert({max(v, d+w), b});
            } else {
                if (d+w > seconddist[b]) {
                    continue;
                }
                pq.erase({seconddist[b], b});
                if (d+w < bestdist[b]) {
                    seconddist[b] = bestdist[b];
                    bestdist[b] = d+w;
                } else {
                    seconddist[b] = d+w;
                }
                pq.insert({seconddist[b], b});
            }
        }
    }
    return seconddist[0];
}

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