Submission #371303

#	Time	Username	Problem	Language	Result	Execution time	Memory
371303		peijar	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	642 ms	87732 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
#define SZ(v) ((int)(v).size())
using namespace std;
using ll = long long;

template<class Fun>
class y_combinator_result {
	Fun fun_;
	public:
	template<class T>
		explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

	template<class ...Args>
		decltype(auto) operator()(Args &&...args) {
			return fun_(std::ref(*this), std::forward<Args>(args)...);
		}
};
template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	vector<vector<pair<int, int>>> g(N);
	for (int i(0); i < M; ++i)
	{
		int u = R[i][0], v = R[i][1];
		g[u].emplace_back(v, L[i]);
		g[v].emplace_back(u, L[i]);
	}
	vector<bool> isBlocked(N);
	for (int i(0); i < K; ++i)
		isBlocked[P[i]] = true;
	priority_queue<tuple<ll, int, int>> pq;
	vector<int> nbPass(N);
	vector<int> pass(N, -1);
	for (int i(0); i < N; ++i)
		if (isBlocked[i])
		{
			pq.push({0, i, i});
			nbPass[i] = 1;
		}
	while (!pq.empty())
	{
		auto [d, u, from] = pq.top(); pq.pop();
		if (nbPass[u] == 2)
			continue;
		if (pass[u] == from)
			continue;
		nbPass[u]++;
		pass[u] = from;
		d = -d;
		if (nbPass[u] == 2 and !u)
			return d;
		if (nbPass[u] == 1)
			continue;
		for (auto [v,w] : g[u])
			pq.push({-(d + w), v, u});
	}
	assert(false);
	return -1;
}

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