Submission #1182464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182464		boclobanchat	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	346 ms	73076 KiB

crocodile

#include"crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define ii pair<long long,long long>
#define fi first
#define se second
const int MAXN=1e5+5;
const long long INF=1e18;
long long dp[MAXN][2];
vector<ii> ds[MAXN];
int travel_plan(int n,int m,int R[][2],int L[],int k,int P[])
{
	priority_queue< ii,vector<ii>,greater<ii> > pq;
	for(int i=0;i<n;i++) dp[i][0]=dp[i][1]=INF,ds[i].clear();
	for(int i=0;i<m;i++) ds[R[i][0]].push_back({R[i][1],L[i]}),ds[R[i][1]].push_back({R[i][0],L[i]});
	for(int i=0;i<k;i++) dp[P[i]][0]=dp[P[i]][1]=0,pq.push({0,P[i]});
	while(!pq.empty())
	{
		long long a=pq.top().fi,b=pq.top().se;
		pq.pop();
		if(dp[b][1]==INF||dp[b][1]<a) continue;
		for(auto v:ds[b]) if(dp[v.fi][0]>a+v.se)
		{
			if(dp[v.fi][0]<dp[v.fi][1]) pq.push({dp[v.fi][0],v.fi});
			dp[v.fi][1]=dp[v.fi][0],dp[v.fi][0]=a+v.se;
		}
		else if(dp[v.fi][1]>a+v.se)
		{
			dp[v.fi][1]=a+v.se;
			pq.push({dp[v.fi][1],v.fi});
		}
	}
	return dp[0][1];
}

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