Submission #371295

#	Time	Username	Problem	Language	Result	Execution time	Memory
371295		peijar	Crocodile's Underground City (IOI11_crocodile)	C++17	0 / 100	1 ms	364 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;

	vector<int> sol(N, 2e9);

	auto dfs = y_combinator([&](auto dfs, int u, int p) -> void
			{
				if (isBlocked[u])
				{
					sol[u] = 0;
					return ;
				}
				vector<int> possibilities;
				for (auto [v, w] : g[u])
					if (v != p)
					{
						dfs(v, u);
						possibilities.push_back(w + sol[v]);
					}
				sort(possibilities.begin(), possibilities.end());
				assert(SZ(possibilities) >= 2);
				sol[u] = possibilities[0] + possibilities[1];
			});
	dfs(0,0);
  return sol[0];
}

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