Submission #846829

#	Time	Username	Problem	Language	Result	Execution time	Memory
846829		12345678	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	481 ms	72652 KiB

crocodile

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

using namespace std;

const int nx=1e5+5;
int vs[nx], dp[nx];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<vector<pair<int, int>>> d(nx);

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    for (int i=0; i<M; i++) d[R[i][0]].push_back({R[i][1], L[i]}), d[R[i][1]].push_back({R[i][0], L[i]});
    for (int i=0; i<K; i++) pq.push({0, P[i]}), vs[P[i]]=1;
    while (!pq.empty())
    {
        auto [cw, cl]=pq.top();
        //printf("%d %d %d\n", cl, cw, vs[cl]);
        pq.pop();
        if (vs[cl]==2) continue;
        vs[cl]++;
        if (vs[cl]==1) continue;
        dp[cl]=cw;
        for (auto [v, w]:d[cl])
        {
            if (vs[v]!=2) pq.push({dp[cl]+w, v}); 
        }
    }
    return dp[0];
}

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