Submission #94656

#	Time	Username	Problem	Language	Result	Execution time	Memory
94656		andy627	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	730 ms	64376 KiB

crocodile

#include "crocodile.h"

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#define LL long long
#define pll pair<LL,LL>
#define pii pair<int,int>
#define ff first
#define ss second
#define INF 1e18
using namespace std;

int n;
vector<pii> edge[111111];
bool is_esc[111111];

pll dist[111111];
priority_queue<pll,vector<pll>,greater<pll>> pq;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	n=N;
	for(int i=0;i<M;i++){
		edge[R[i][0]].push_back({R[i][1],L[i]});
		edge[R[i][1]].push_back({R[i][0],L[i]});
	}
	for(int i=0;i<K;i++) is_esc[P[i]]=1;

	for(int i=0;i<N;i++){
		if(is_esc[i]) pq.push({0,i});
		else dist[i].ff=dist[i].ss=INF;
	}
	while(!pq.empty()){
		pll p=pq.top(); pq.pop();
		if(p.ff!=dist[p.ss].ss) continue;

		for(pii u:edge[p.ss]){
			if(dist[u.ff].ff>dist[p.ss].ss+u.ss){
				bool sta=(dist[u.ff].ff==dist[u.ff].ss);
				dist[u.ff].ss=dist[u.ff].ff;
				dist[u.ff].ff=dist[p.ss].ss+u.ss;
				if(!sta && dist[u.ff].ss!=INF) pq.push({dist[u.ff].ss,u.ff});
			}
			else if(dist[u.ff].ss>dist[p.ss].ss+u.ss){
				dist[u.ff].ss=dist[p.ss].ss+u.ss;
				pq.push({dist[u.ff].ss,u.ff});
			}
		}
	}

	return dist[0].ss;
}

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