Submission #574240

#	Time	Username	Problem	Language	Result	Execution time	Memory
574240		mosiashvililuka	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	546 ms	88452 KiB

crocodile

#include<bits/stdc++.h>
#include "crocodile.h"
using namespace std;
const int N=1000000004;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,K,P[100009],bo[100009];
vector <pair <long long, long long> > v[100009];
priority_queue <pair <long long, long long> > s;
pair <long long, long long> dis[100009],PA;
void UPD(long long q, long long w){
    if(dis[q].first>w){
        dis[q].second=dis[q].first;dis[q].first=w;
    }else{
        if(dis[q].second>w) dis[q].second=w;
    }
}
int travel_plan(int NN, int MM, int RR[][2], int LL[], int KK, int PP[])
{
    a=NN;b=MM;
    for(i=1; i<=b; i++){
        c=RR[i-1][0]+1;d=RR[i-1][1]+1;e=LL[i-1];
        v[c].push_back({d,e});v[d].push_back({c,e});
    }
    K=KK;
    for(i=1; i<=K; i++){
        P[i]=PP[i-1]+1;
    }
    for(i=0; i<=a+1; i++){
        dis[i]={N,N};
    }
    for(i=1; i<=K; i++){
        s.push({0,P[i]});
        dis[P[i]]={0,0};
    }
    while(s.size()){
        while(s.size()){
            PA=s.top();
            if(bo[PA.second]==1){
                s.pop();
            }else{
                break;
            }
        }
        if(s.size()==0) break;
        c=PA.second;d=-PA.first;s.pop();bo[c]=1;
        for(vector <pair <long long, long long> >::iterator it=v[c].begin(); it!=v[c].end(); it++){
            if(dis[(*it).first].second>dis[c].second+(*it).second){
                UPD((*it).first,dis[c].second+(*it).second);
                s.push({-dis[(*it).first].second,(*it).first});
            }
        }
    }
    return dis[1].second;
}

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