Submission #1216367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216367		InvMOD	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	295 ms	48792 KiB

crocodile

#include<bits/stdc++.h>

using namespace std;

#ifndef name
    #include "crocodile.h"
#endif // name

#define pi pair<int,int>
#define sz(v) (int)(v).size()


int travel_plan(int n, int m, int R[][2], int L[], int K, int P[]){
    vector<vector<pi>> adj(n, vector<pi>());

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

    const int inf = 1e9 + 1;
    vector<vector<int>> dist(n, vector<int>(2, inf));
    for(int i = 0; i < K; i++){
        int x = P[i];
        dist[x][0] = 0;
        dist[x][1] = 0;
    }

    priority_queue<pi> pq;
    for(int i = 0; i < K; i++) pq.emplace(0, P[i]);

    vector<bool> vis(n + 1, false);
    while(!pq.empty()){
        pi eq = pq.top(); pq.pop();

        int cur_dist = -eq.first, x = eq.second;
        if(vis[x] || cur_dist == inf) continue;

        vis[x] = true;
        for(pi e : adj[x]){
            int v = e.first, w = e.second;

            if(dist[x][1] + w < dist[v][0]){
                dist[v][1] = dist[v][0];
                dist[v][0] = dist[x][1] + w;

                pq.emplace(-dist[v][1], v);
            }
            else if(dist[x][1] + w < dist[v][1]){
                dist[v][1] = cur_dist + w;

                pq.emplace(-dist[v][1], v);
            }
        }
    }

    return dist[0][1];
}

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