Submission #212830

#	Time	Username	Problem	Language	Result	Execution time	Memory
212830		faremy	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1835 ms	263216 KiB

bitaro

#include <iostream>
#include <algorithm>
#include <vector>


struct Beaver
{
	Beaver(int i, int d) : id(i), dist(d) {}
	int id, dist;
};

const int MAXN = 1e5;
const int SQRT = 317;

std::vector<int> graph[MAXN];
std::vector<Beaver> furthest[MAXN];
bool seen[MAXN];
bool busy[MAXN];
int maxDist[MAXN];


void append(std::vector<Beaver> &vec, Beaver elem)
{
	if (!seen[elem.id])
	{
		vec.emplace_back(elem);
		seen[elem.id] = true;
	}
}

void merge(int parent, int child)
{
	std::vector<Beaver> merged;
	int left = 0, right = 0;

	while (merged.size() < SQRT && (left < (int)furthest[parent].size() || right < (int)furthest[child].size()))
	{
		if (left == (int)furthest[parent].size())
		{
			append(merged, Beaver(furthest[child][right].id, furthest[child][right].dist + 1));
			right++;
		}
		else if (right == (int)furthest[child].size())
		{
			append(merged, furthest[parent][left]);
			left++;
		}
		else if (furthest[parent][left].dist > furthest[child][right].dist + 1)
		{
			append(merged, furthest[parent][left]);
			left++;
		}
		else
		{
			append(merged, Beaver(furthest[child][right].id, furthest[child][right].dist + 1));
			right++;
		}
	}

	for (Beaver beav : merged)
		seen[beav.id] = false;
	furthest[parent] = merged;
}

int slowcheck(int node)
{
	if (seen[node])
		return maxDist[node];
	seen[node] = true;

	if (busy[node])
		maxDist[node] = -1;
	else
		maxDist[node] = 0;

	for (int child : graph[node])
	{
		int sub = slowcheck(child);
		if (sub != -1)
			maxDist[node] = std::max(maxDist[node], sub + 1);
	}

	return maxDist[node];
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cout.tie(nullptr);
	std::cin.tie(nullptr);

	int nodes, edges, queries;
	std::cin >> nodes >> edges >> queries;

	for (int iEdge = 0; iEdge < edges; iEdge++)
	{
		int u, v;
		std::cin >> u >> v;
		graph[v - 1].emplace_back(u - 1);
	}

	for (int iNode = 0; iNode < nodes; iNode++)
	{
		furthest[iNode].emplace_back(iNode, 0);
		for (int child : graph[iNode])
			merge(iNode, child);
	}

	for (int iQuery = 0; iQuery < queries; iQuery++)
	{
		int location, unable;
		std::cin >> location >> unable;
		location--;

		std::vector<int> notComing;
		for (int iFriend = 0; iFriend < unable; iFriend++)
		{
			int beaver; std::cin >> beaver;
			notComing.emplace_back(beaver - 1);
			busy[beaver - 1] = true;
		}

		if (unable < SQRT)
		{
			int far = 0;
			while (far < (int)furthest[location].size() && busy[furthest[location][far].id])
				far++;

			if (far == (int)furthest[location].size())
				std::cout << "-1\n";
			else
				std::cout << furthest[location][far].dist << '\n';
		}
		else
		{
			std::fill_n(seen, nodes, false);
			std::cout << slowcheck(location) << '\n';
		}

		for (int beaver : notComing)
			busy[beaver] = false;
	}

	return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86