Submission #568194

#	Time	Username	Problem	Language	Result	Execution time	Memory
568194		n0sk1ll	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	1091 ms	92012 KiB

crocodile

#include "crocodile.h"

#include <bits/stdc++.h>

#define xx first
#define yy second

using namespace std;
long long int typedef li;

vector<vector<pair<int,int>>> g(100003);
li dp[100003]; bitset<100003> vis,izlaz;

int travel_plan(int n, int m, int R[][2], int L[], int K, int P[])
{
    for (int i=0;i<m;i++)
    {
        g[R[i][0]].push_back({L[i],R[i][1]});
        g[R[i][1]].push_back({L[i],R[i][0]});
    }

    priority_queue<pair<li,int>,vector<pair<li,int>>,greater<pair<li,int>>> pq;
    for (int i=0;i<K;i++) pq.push({0,P[i]}),vis[P[i]]=1;
    while (!pq.empty())
    {
        li d=pq.top().xx;
        int p=pq.top().yy;
        pq.pop();

        if (dp[p]) continue;
        if (izlaz[p]) continue;
        if (vis[p])
        {
            dp[p]=d,izlaz[p]=1;
            for (auto it : g[p]) pq.push({dp[p]+it.xx,it.yy});
        }
        else vis[p]=1;
    }
    return dp[0];
}

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