Submission #799890

#	Time	Username	Problem	Language	Result	Execution time	Memory
799890		Sohsoh84	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	470 ms	62700 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pll;

#define X		first
#define Y		second
#define sep		' '
#define all(x)		(x).begin(), (x).end()
#define debug(x)	cerr << #x << ": " << x << endl;

const ll MAXN = 1e5 + 10;
const ll INF = 1e9 + 10;

ll dist[MAXN], n, m;
vector<pll> adj[MAXN];
priority_queue<pll, vector<pll>, greater<pll>> pq;
pair<pll, pll> F[MAXN];

inline void check(int v) {
	if (F[v].Y.X < dist[v]) {
		dist[v] = F[v].Y.X; 
		pq.push({dist[v], v});
	}
}

inline void add(pair<pll, pll>& a, pll e) {
	vector<pll> vec = {a.X, a.Y, e};
	sort(all(vec), less<pll>());
	a.X = vec[0];
	if (vec[1].Y == a.X.Y) a.Y = vec[2];
	else a.Y = vec[1];
}

inline void fix(int v) {
	for (auto [u, l] : adj[v]) {
		add(F[u], {dist[v] + l, v});
		check(u);
	}
} 

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	n = N, m = M;
	for (int 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]});
	}

	fill(dist, dist + MAXN, INF);
	fill(F, F + MAXN, make_pair(pll(INF, INF), pll(INF, INF)));

	for (int i = 0; i < K; i++) {
		int v = P[i];
		dist[v] = 0;
		pq.push({0, v});
	}

	while (!pq.empty()) {
		auto [d_v, v] = pq.top();
		pq.pop();
		if (d_v != dist[v]) continue;
		fix(v);
	}

	dist[0] = min(dist[0], ll(numeric_limits<int>::max()));
	return dist[0];
}

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