제출 #1177623

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177623		qrn	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	1345 ms	118608 KiB

crocodile

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

#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);

#define pb push_back
#define ins insert
#define fi first
#define se second

#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define sz(x) x.size()
#define intt int

const intt mod = 1e9 + 7;
const intt base = 31;
const intt inf = 1e9;
const intt mxN = 1e6 + 5;
const intt l = 21;


intt travel_plan(intt N, intt M, intt R[][2], intt L[], intt K, intt P[]) {
    intt isexit[N+1], D[N+1][2];
    set<pair<intt,intt>> graph[2 * N+1];

    for(intt i = 0; i < N; i++) {
        D[i][0] = D[i][1] = inf;
        isexit[i] = 0;
    }

    for(intt i = 0; i < K; i++) {
        isexit[P[i]] = 1;
    }
    
    for(intt i = 0; i < M; i++) {
        intt a = R[i][0], b = R[i][1];
        graph[a].insert({b, L[i]});
        graph[b].insert({a, L[i]});
    }

    priority_queue<pair<intt,intt>, vector<pair<intt,intt>>, greater<pair<intt,intt>>> pq;

    for(intt i = 0; i < N; i++) {
        if(isexit[i]) {
            pq.push({0, i});
            D[i][0] = D[i][1] = 0;
        }
    }

    while(not pq.empty()) {
        intt d = pq.top().fi;
        intt cur = pq.top().se;
        pq.pop();
        if(max(D[cur][0], D[cur][1]) < d) continue;

        for(auto g : graph[cur]) {
            intt u = g.fi, W = g.se;
            if(max(D[u][0], D[u][1]) <= d + W) continue;
            
            if(D[u][0] > d + W) {
                if(D[u][0] < D[u][1]) {
                    pq.push({D[u][0], u});
                }
                D[u][1] = D[u][0];
                D[u][0] = d + W;
            } else if(D[u][1] > d + W) {
                D[u][1] = d + W;
                pq.push({D[u][1], u});
            }
        }
    }

    return D[0][1];
}

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