Submission #493601

#	Time	Username	Problem	Language	Result	Execution time	Memory
493601		ahmeteren	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	474 ms	61912 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

const int NNN = 1e5 + 5;

long long dist1[NNN], dist2[NNN];
vector<pair<int, int>> vec[NNN];

int travel_plan(int n, int m, int R[][2], int L[], int K, int P[])
{
    for(int i = 0; i < n; i++)
        dist1[i] = dist2[i] = 1e12;

    for(int i = 0; i < m; i++)
    {
        int u = R[i][0], v = R[i][1], w = L[i];

        vec[u].push_back({v, w});
        vec[v].push_back({u, w}); 
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

    for(int i = 0; i < K; i++)
    {
        q.push({0, P[i]});
        dist1[P[i]] = dist2[P[i]] = 0;
    }

    while(!q.empty())
    {
        long long node = q.top().second, dst = q.top().first;
        q.pop();

        if(dst > dist2[node])
            continue;

        for(auto p : vec[node])
        {
            long long to = p.first, w = p.second;

            if(dst + w < dist1[to])
            {
                if(dist1[to] < dist2[to])
                {
                    dist2[to] = dist1[to];
                    dist1[to] = dst + w;
                    q.push({dist2[to], to});
                }
                else
                {
                    dist2[to] = dist1[to];
                    dist1[to] = dst + w;
                }
            }
            else if(dst + w < dist2[to])
            {
                dist2[to] = dst + w;
                q.push({dist2[to], to});
            }
        }
    }

    return dist2[0];
}

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