Submission #1269369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269369		dhuyyyy	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	375 ms	77116 KiB

crocodile

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using aa = array<int,3>;
using ii = pair<int,int>;

const int N = 1e5+5;
const int MOD = 1e9+7;

int v, u, kc, d[N][2];

bool vis[N];

vector <ii> adj[N];

priority_queue<ii,vector<ii>,greater<ii>> pq;

signed travel_plan(signed N,signed M,signed R[][2],signed L[],signed K,signed P[]){
    for (int i = 0; i < M; i++){
        R[i][0]++;
        R[i][1]++;
        adj[R[i][0]].push_back({R[i][1],L[i]});
        adj[R[i][1]].push_back({R[i][0],L[i]});
    }
    for (int i = 1; i <= N; i++){
        d[i][0] = 1e18;
        d[i][1] = 1e18;
    }
    for (int i = 0; i < K; i++){
        P[i]++;
        d[P[i]][0] = d[P[i]][1] = 0;
        pq.push({0,P[i]});
    }
    while (!pq.empty()){
        tie(kc,u) = pq.top();
        pq.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (ii it : adj[u]){
            v = it.fi;
            int tmp = kc + it.se;
            if (tmp < d[v][1]){
                d[v][1] = tmp;
                if (d[v][0] > d[v][1]) swap(d[v][0],d[v][1]);
                pq.push({d[v][1],v});
            }
        }
    }
    return d[1][1];
}

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