oj.uz

Submission #371296

# Submission time Handle Problem Language Result Execution time Memory
371296 2021-02-26T12:16:14 Z peijar Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 180 ms 262148 KB 
#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<ll> sol(N);

	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[1];
			});
	dfs(0,0);
  return (int)sol[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Runtime error 180 ms 262148 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Runtime error 180 ms 262148 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -