Submission #371054

#	Time	Username	Problem	Language	Result	Execution time	Memory
371054		Peti	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	873 ms	101024 KiB

crocodile

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

using namespace std;

vector<vector<pair<int, long long>>> g;
vector<bool> volt[2];
vector<long long> tav;

void dijkstra(vector<int> v){
    priority_queue<pair<long long, int>> pq;

    for(int i = 0; i < (int)v.size(); i++){
        volt[0][v[i]] = true;
        pq.push(make_pair(0, v[i]));
    }

    while(pq.size() > 0){
        while(pq.size() > 0 && volt[0][pq.top().second] && volt[1][pq.top().second])
            pq.pop();
        if(pq.size() == 0)
            break;
        int x = pq.top().second;
        long long y = -pq.top().first;
        pq.pop();
        if(!volt[0][x]){
            volt[0][x] = true;
            continue;
        }else{
            volt[1][x] = true;
            tav[x] = y;
        }

        for(pair<int, long long> e : g[x])
            if(!volt[1][e.first])
                pq.push(make_pair(-(y + e.second), e.first));
    }
    return;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    g.resize(N);
    volt[0].resize(N, false);
    volt[1].resize(N, false);
    tav.resize(N, (long long)1e18);

    for(int i = 0; i < M; i++){
        g[R[i][0]].push_back(make_pair(R[i][1], L[i]));
        g[R[i][1]].push_back(make_pair(R[i][0], L[i]));
    }

    vector<int> v;
    for(int i = 0; i < K; i++)
        v.push_back(P[i]);
    dijkstra(v);

    return tav[0];
}

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