Submission #1123504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123504		pcc	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	665 ms	83624 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<ll,ll>
#define pll pii
#define fs first
#define sc second

const ll inf = 1e18;
const int mxn = 2e5+10;
bool vis[mxn];
vector<pii> paths[mxn];
ll dis[mxn][2];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	for(int i = 0;i<=N;i++)dis[i][0] = dis[i][1] = inf;
	for(int i = 0;i<M;i++){
		int a = R[i][0],b = R[i][1],c = L[i];
		paths[a].push_back(pii(b,c));
		paths[b].push_back(pii(a,c));
	}
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	for(int i = 0;i<K;i++){
		int now = P[i];
		dis[now][0] = dis[now][1] = 0;
		pq.push(pii(0,now));
	}
	while(!pq.empty()){
		auto [d,now] = pq.top();
		pq.pop();
		if(vis[now])continue;
		vis[now] = 1;
		for(auto [nxt,w]:paths[now]){
			if(vis[nxt])continue;
			if(dis[nxt][0]>d+w){
				swap(dis[nxt][0],dis[nxt][1]);
				dis[nxt][0] = d+w;
			}
			else if(dis[nxt][1]>d+w)dis[nxt][1] = d+w;
			if(dis[nxt][1] != inf)pq.push(pll(dis[nxt][1],nxt));
		}
	}
	return dis[0][1];
}

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