Submission #1005725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005725		ayankarimova	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	393 ms	105236 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define pll pair<ll, ll>
const ll sz=1e5+5, inf=1000000000000000020;
ll c[sz][2LL], used[sz];
vector<pll>g[sz];
priority_queue<pll, vector<pll>, greater<pll>>q;
/*
{} []
*/
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
    for(int i=0; i<m; i++){
        ll u=r[i][0], v=r[i][1];
        g[u].push_back({v, l[i]});
        g[v].push_back({u, l[i]});
    }
    for(int i=0; i<n; i++){
        c[i][0]=inf;
        c[i][1]=inf;
    }
    for(int i=0; i<k; i++){
        c[p[i]][0]=0;
        c[p[i]][1]=0;
        q.push({0, p[i]});
    }
    while(q.size()){
        ll u=q.top().second, dis=q.top().first;
        q.pop();
        if(used[u]) continue;
        used[u]=1;
        if(dis>=inf) continue;
        for(auto i:g[u]){
            ll v=i.first, w=i.second;
            if(!used[v]){
                if(dis+w<c[v][0]){
                    c[v][1]=c[v][0];
                    c[v][0]=dis+w;
                }
                else c[v][1]=min(c[v][1], dis+w);
                q.push({c[v][1], v});
            }
        }
    }
    return c[0][1];
}

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