Submission #540216

#	Time	Username	Problem	Language	Result	Execution time	Memory
540216		status_coding	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	1546 ms	130200 KiB

crocodile

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

using namespace std;

bool open[100005];
long long dp[100005];

vector<pair<long long, long long>> v[100005];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
    for(int i=0;i<n;i++)
    {
        dp[i]=-1;
        open[i]=false;
    }

    for(int i=0;i<m;i++)
    {
        v[ r[i][0] ].push_back({r[i][1], l[i]});
        v[ r[i][1] ].push_back({r[i][0], l[i]});
    }

    multiset<pair<long long, int>> s;

    for(int i=0;i<k;i++)
    {
        open[ p[i] ] = true;
        s.insert({0, p[i]});
    }

    while(!s.empty())
    {
        int x = s.begin()->second;
        long long len = s.begin()->first;
        s.erase(s.begin());

        if(!open[x])
        {
            open[x]=true;
            continue;
        }

        if(dp[x] != -1)
            continue;

        dp[x]=len;

        for(auto it : v[x])
        {
            if(dp[it.first] == -1)
                s.insert({len + it.second, it.first});
        }
    }

    return dp[0];
}

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