Submission #50991

#	Time	Username	Problem	Language	Result	Execution time	Memory
50991		win11905	Crocodile's Underground City (IOI11_crocodile)	C++11	100 / 100	828 ms	45112 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;

const int MXN = 1e5+5, INF = 1e9+1;

pii d[MXN];
vector<vector<pii> > g(MXN);

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	for(int i = 0, u, v, w; i < M; ++i) {
		u = R[i][0], v = R[i][1], w = L[i];
		g[u].emplace_back(v, w), g[v].emplace_back(u, w);
	}
	fill(d, d+N, pii(INF, INF));
	priority_queue<pii, vector<pii>, greater<pii> > Q;
	for(int i = 0; i < K; ++i) d[P[i]] = pii(0, 0), Q.emplace(0, P[i]);
	while(!Q.empty()) {
		pii now = Q.top(); Q.pop();
		if(d[now.y].y != now.x) continue;
		for(auto v : g[now.y]) {
			int z = now.x + v.y;
			if(d[v.x].x > z) swap(d[v.x].x, z);
			if(d[v.x].y > z) swap(d[v.x].y, z), Q.emplace(d[v.x].y, v.x);
		}
	}
	return d[0].y;
}

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