제출 #406478

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
406478		Falcon	악어의 지하 도시 (IOI11_crocodile)	C++17	100 / 100	869 ms	96372 KiB

crocodile

#include "crocodile.h"
#include <vector>
#include <queue>
#include <array>

using namespace std;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    vector<vector<pair<int, long long>>> adj(N);
    for(int i{}; i < M; ++i) {
        adj[R[i][0]].push_back({R[i][1], L[i]});
        adj[R[i][1]].push_back({R[i][0], L[i]});
    }
    
    priority_queue<pair<long long, int>,
                   vector<pair<long long, int>>,
                   greater<pair<long long, int>>> pq;

    vector<long long> dist(N, -1);
    vector<int> processed_neighbours(N);
    vector<array<long long, 2>> paths(N);
    vector<bool> processed(N);

    for(int i{}; i < K; ++i)
        dist[P[i]] = 0, pq.push({0, P[i]});

    auto update = [&](int u, long long d) {
        if(processed[u]) return;
        switch(processed_neighbours[u]) {
            case 0:
                paths[u][0] = d;
                break;
            case 1:
                paths[u][1] = d;
                if(paths[u][1] < paths[u][0])
                    swap(paths[u][1], paths[u][0]);
                pq.push({paths[u][1], u});
                break;
            default:
                if(d < paths[u][1])
                    paths[u][1] = d;
                if(paths[u][1] < paths[u][0])
                    swap(paths[u][1], paths[u][0]);
                pq.push({paths[u][1], u});
                break;
        }
        ++processed_neighbours[u];
    };

    while(!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if(processed[u])
            continue;
        processed[u] = true;
        dist[u] = d;
        for(auto [v, w]: adj[u])
            update(v, d + w);
    }

    return int(dist[0]);
}

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