Submission #604257

#	Time	Username	Problem	Language	Result	Execution time	Memory
604257		penguinhacker	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	470 ms	61136 KiB

crocodile

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

#define ar array

const int mxN=1e5;
int n, m, d[mxN][2];
vector<ar<int, 2>> adj[mxN];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	n=N, m=M;
	for (int i=0; i<m; ++i) {
		int u=R[i][0], v=R[i][1], w=L[i];
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	memset(d, 0x3f, sizeof(d));
	priority_queue<ar<int, 2>, vector<ar<int, 2>>, greater<ar<int, 2>>> pq;
	for (int i=0; i<K; ++i) {
		int u=P[i];
		d[u][0]=d[u][1]=0;
		pq.push({0, u});
	}
	while(pq.size()) {
		int cd=pq.top()[0], u=pq.top()[1];
		pq.pop();
		if (cd!=d[u][1])
			continue;
		for (auto [v, w] : adj[u]) {
			int last=d[v][1];
			if (cd+w<d[v][0])
				d[v][1]=d[v][0], d[v][0]=cd+w;
			else if (cd+w<d[v][1])
				d[v][1]=cd+w;
			if (d[v][1]<last)
				pq.push({d[v][1], v});
		}
	}
	return d[0][1];
}

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