Submission #1073828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073828		ssitaram	Crocodile's Underground City (IOI11_crocodile)	C++17	89 / 100	291 ms	76744 KiB

crocodile

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

typedef long long ll;

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
	vector<vector<pair<ll, ll>>> adj(n);
	for (ll i = 0; i < m; ++i) {
		adj[r[i][0]].push_back({r[i][1], l[i]});
		adj[r[i][1]].push_back({r[i][0], l[i]});
	}
	priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
	vector<priority_queue<ll>> best2(n);
	for (ll i = 0; i < k; ++i) {
		pq.push({0, p[i]});
		best2[p[i]].push(0);
		best2[p[i]].push(0);
	}
	while (!pq.empty()) {
		pair<ll, ll> state = pq.top();
		pq.pop();
		if (state.first > best2[state.second].top()) continue;
		if (!state.second) {
			return state.first;
		}
		for (pair<ll, ll>& edge : adj[state.second]) {
			if (best2[edge.first].size() < 2) {
				best2[edge.first].push(state.first + edge.second);
				if (best2[edge.first].size() == 2) pq.push({best2[edge.first].top(), edge.first});
			} else if (state.first + edge.second < best2[edge.first].top()) {
				best2[edge.first].pop();
				best2[edge.first].push(state.first + edge.second);
				pq.push({best2[edge.first].top(), edge.first});
			}
		}
	}
	return 0;
}

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