Submission #1200050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200050		IBory	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	703 ms	101672 KiB

crocodile

#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;

const int MAX = 100007;
vector<pii> G[MAX];
ll D[MAX], V[MAX];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	for (int i = 0; i < M; ++i) {
		ll a = R[i][0], b = R[i][1], c = L[i];
		G[a].emplace_back(b, c);
		G[b].emplace_back(a, c);
	}

	priority_queue<pii, vector<pii>, greater<pii>> PQ;
	memset(D, 0x3f, sizeof(D));
	while (K--) {
		int n = P[K];
		V[n] = 1;
		PQ.emplace(0, n);
	}

	while (!PQ.empty()) {
		auto [cd, cur] = PQ.top(); PQ.pop();
		if (++V[cur] != 2) continue;
		D[cur] = cd;
		for (auto [next, nd] : G[cur]) PQ.emplace(cd + nd, next);
	}

	return D[0];
}

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