oj.uz

Submission #371303

# Submission time Handle Problem Language Result Execution time Memory
371303 2021-02-26T12:34:36 Z peijar Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 642 ms 87732 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;
	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.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 620 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 1 ms 492 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 620 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 1 ms 492 KB Output is correct
9 Correct 2 ms 748 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 2 ms 620 KB Output is correct
12 Correct 7 ms 1520 KB Output is correct
13 Correct 6 ms 1512 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 2 ms 492 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 620 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 1 ms 492 KB Output is correct
9 Correct 2 ms 748 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 2 ms 620 KB Output is correct
12 Correct 7 ms 1520 KB Output is correct
13 Correct 6 ms 1512 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Correct 597 ms 87732 KB Output is correct
17 Correct 100 ms 13804 KB Output is correct
18 Correct 111 ms 15340 KB Output is correct
19 Correct 640 ms 75600 KB Output is correct
20 Correct 391 ms 80208 KB Output is correct
21 Correct 59 ms 6252 KB Output is correct
22 Correct 642 ms 45540 KB Output is correct