Submission #919934

#	Time	Username	Problem	Language	Result	Execution time	Memory
919934		Lobo	Crocodile's Underground City (IOI11_crocodile)	C++17	89 / 100	430 ms	83120 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fr first
#define sc second
#define int long long
const int maxn = 1e5+10;
const int inf = 1e18+10;


int32_t travel_plan(int32_t n, int32_t m, int32_t R[][2], int32_t L[], int32_t k, int32_t P[])
{
	vector<vector<pair<int,int>>> g(n);
	for(int i = 0; i < m; i++) {
		g[R[i][0]].pb(mp(R[i][1],L[i]));
		g[R[i][1]].pb(mp(R[i][0],L[i]));
	}

	vector<int> d1(n),d2(n);
	for(int i = 0; i < n; i++) {
		d1[i] = d2[i] = inf;
	}
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	for(int i = 0; i < k; i++) {
		int v = P[i];
		d1[v] = d2[v] = 0;
		pq.push(mp(0,v));
	}

	while(pq.size()) {
		int u = pq.top().sc;
		int dis2 = pq.top().fr;
		pq.pop();
		if(dis2 != d2[u]) continue;

		for(auto V : g[u]) {
			int v = V.fr;
			int w = V.sc;
			if(d2[v] > d2[u]+w) {
				d2[v] = d2[u]+w;
				if(d2[v] < d1[v]) swap(d2[v],d1[v]);
				if(d2[v] != inf) pq.push(mp(d2[v],v));
			}
		}
	}

	return (int32_t) d2[0];
}

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