Submission #799744

#	Time	Username	Problem	Language	Result	Execution time	Memory
799744		Liudas	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	657 ms	75512 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    //cout << "??" << endl;
    vector<pair<int, int>> tree[N];
    for(int i = 0; i < M; i ++){
        tree[R[i][0]].push_back({R[i][1], L[i]});
        tree[R[i][1]].push_back({R[i][0], L[i]});
    }
   // cout << "???" << endl;
    priority_queue<pair<int, int>> que;
    vector<int> dist(N, 1e9), cc(N);
    for(int i = 0; i < K; i++){
        cc[P[i]] = 2;
        for(auto [l ,r] : tree[P[i]])
            que.push({-r, l});
    }
    while(!que.empty()){
        int a = -que.top().first, b = que.top().second;
        //cout << b << " " << a << endl;
        que.pop();
        if(cc[b] != 1){
            cc[b]++;
            continue;
        }
        cc[b]++;
        dist[b] = a;
        for(auto [l, r] : tree[b]){
            que.push({-r-a, l});
        }
    }
    return dist[0];
}

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