Submission #392938

#	Time	Username	Problem	Language	Result	Execution time	Memory
392938		Aryan_Raina	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	645 ms	72796 KiB

crocodile

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

#define ar array
#define ll long long
const ll INF = 1e15;
int travel_plan(int n, int m, int R[][2], int L[], int k, int P[]) {
	vector<ar<ll,2>> g[n];

	for (ll i = 0; i < m; i++) {
		g[R[i][0]].push_back({L[i], R[i][1]});
		g[R[i][1]].push_back({L[i], R[i][0]});
	}

	vector<ll> d1(n, INF), d2(n, INF);
	priority_queue<ar<ll,2>, vector<ar<ll,2>>, greater<ar<ll,2>>> pq;
	for (ll i = 0; i < k; i++) pq.push({d1[P[i]] = d2[P[i]] = 0, P[i]});

	vector<bool> vis(n, false);
	while (!pq.empty()) {
		ll u = pq.top()[1], dist = pq.top()[0]; pq.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (auto v : g[u]) {
			if (dist + v[0] < d1[v[1]]) d2[v[1]] = d1[v[1]], d1[v[1]] = dist + v[0];
			else if (dist + v[0] < d2[v[1]]) d2[v[1]] = dist + v[0];
			else continue;
			if (d2[v[1]] <= INF/2) pq.push({d2[v[1]], v[1]});
		}
	}
	return d2[0];
}

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