답안 #371303

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
371303	2021-02-26T12:34:36 Z	peijar	악어의 지하 도시 (IOI11_crocodile)	C++17	100 / 100	642 ms	87732 KB

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.0 / 46.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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