Submission #669169

#	Time	Username	Problem	Language	Result	Execution time	Memory
669169		ljuba	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	428 ms	52736 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[]) {
    vector<bool> vis(n, false);

    vector<vector<pair<int, int>>> adj(n);

    for(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]});
    }

    vector<int> cnt(n);

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

    for(int i = 0; i < K; ++i) {
        int x = P[i];
        vis[x] = true;

        for(auto e : adj[x]) {
            pq.push({e.second, e.first});
        }
    }

    while(!pq.empty()) {
        auto tren = pq.top();
        pq.pop();

        if(vis[tren.second]) continue;

        ++cnt[tren.second];

        if(cnt[tren.second] == 2) {
            if(tren.second == 0) {
                return tren.first;
            }

            vis[tren.second] = true;

            for(auto e : adj[tren.second]) {
                if(vis[e.first]) continue;
                pq.push({tren.first + e.second, e.first});
            }
        }
    }

    return -1;
}

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