Submission #1308484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308484		StefanSebez	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	276 ms	48544 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=1e5+50,inf=1e9;
const ll INF=1e18;
vector<pair<int,int>>E[N];
int n,m;
ll res[N];
ll mn1[N],mn2[N];
int travel_plan(int n1, int m1, int R[][2], int L[], int K, int P[]){
    n=n1,m=m1;
    for(int i=0;i<m;i++){
        E[R[i][0]].pb({R[i][1],L[i]});
        E[R[i][1]].pb({R[i][0],L[i]});
    }
    for(int i=0;i<n;i++)res[i]=mn1[i]=mn2[i]=INF;
    priority_queue<pair<ll,int>>pq;
    for(int i=0;i<K;i++){
        int u=P[i];
        res[u]=0;
        pq.push({-res[u],u});
    }
    while(!pq.empty()){
        auto [d,u]=pq.top();pq.pop();
        if(-d!=res[u])continue;
        for(auto [v,w]:E[u]){
            ll x=res[u]+w;
            if(x<=mn1[v])mn2[v]=mn1[v],mn1[v]=x;
            else if(x<=mn2[v])mn2[v]=x;
            if(mn2[v]<res[v]){
                res[v]=mn2[v];
                pq.push({-res[v],v});
            }
        }
    }
    return res[0];
}

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