Submission #836757

#	Time	Username	Problem	Language	Result	Execution time	Memory
836757		Elias	Race (IOI11_race)	C++17	21 / 100	3038 ms	121156 KiB

race

#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()

vector<vector<pair<int, int>>> adj;
vector<bool> blocked;

int best = INT32_MAX;
int k;

struct Tree
{
	int n = 0;

	int centroid = -1;

	unordered_map<int, int> subtree;

	void spread(int i, int p = -1)
	{
		n++;
		for (auto [c, D] : adj[i])
		{
			if (c != p && !blocked[c])
			{
				spread(c, i);
			}
		}
	}

	int find_centroid(int i, int p = -1)
	{
		int subtree_size = 1;
		int largest_subtree = 0;

		for (auto [c, D] : adj[i])
		{
			if (c != p && !blocked[c])
			{
				int sub = find_centroid(c, i);
				subtree_size += sub;
				largest_subtree = max(largest_subtree, sub);
			}
		}

		if (largest_subtree <= n / 2 && n - subtree_size <= n / 2)
			centroid = i;

		return subtree[i] = subtree_size;
	}

	unordered_map<int, multiset<int>> dfs(int i, int d = 0, int depth = 0, int p = -1)
	{
		unordered_map<int, multiset<int>> out;
		out[d].insert(depth);

		int subtree_size = 1;

		for (auto [c, D] : adj[i])
		{
			if (c != p && !blocked[c])
			{
				auto child = dfs(c, d + D, depth + 1, i);

				if (subtree[c] > subtree_size)
				{
					swap(child, out);
				}

				for (auto &[a, b] : child)
				{
					for (auto x : b)
						out[a].insert(x);
				}
				subtree_size += subtree[c];
			}
		}

		return out;
	}

	vector<int> split()
	{
		blocked[centroid] = true;
		vector<int> out;
		for (auto [c, d] : adj[centroid])
		{
			if (!blocked[c])
				out.push_back(c);
		}
		return out;
	}

	Tree(int start)
	{
		spread(start);

		find_centroid(start);

		assert(centroid != -1);

		vector<unordered_map<int, multiset<int>>> seperate;

		for (auto [c, d] : adj[centroid])
		{
			seperate.push_back(dfs(c, d, 1, centroid));
		}

		unordered_map<int, multiset<int>> all;
		all[0].insert(0);

		for (auto &child : seperate)
		{
			for (auto &[a, b] : child)
				for (auto x : b)
				{
					all[a].insert(x);
				}
		}

		for (auto &child : seperate)
		{
			for (auto &[a, b] : child)
				for (auto x : b)
				{
					all[a].erase(all[a].find(x));
				}

			for (auto &[a, b] : child)
			{
				if (b.size() == 0)
					continue;
				int other = k - a;

				if (all[other].size())
				{
					best = min(best, *all[other].begin() + *b.begin());
				}
			}

			for (auto &[a, b] : child)
				for (auto x : b)
				{
					all[a].insert(x);
				}
		}
	}
};

#ifndef _DEBUG
#include "race.h"
#else
int best_path(int N, int K, int H[][2], int L[]);
#endif

int best_path(int N, int K, int H[][2], int L[])
{
	adj.resize(N);
	blocked.resize(N);
	k = K;

	for (int i = 0; i < N - 1; i++)
	{
		adj[H[i][1]].push_back(pair<int, int>{H[i][0], L[i]});
		adj[H[i][0]].push_back(pair<int, int>{H[i][1], L[i]});
	}

	vector<Tree> subtrees;
	subtrees.push_back(Tree(0));

	queue<int> todo;
	todo.push(0);

	while (todo.size())
	{
		int index = todo.front();
		todo.pop();

		auto out = subtrees[index].split();
		for (auto x : out)
		{
			Tree new_tree(x);
			if (new_tree.n > 1)
			{
				int new_index = subtrees.size();
				todo.push(new_index);

				subtrees.push_back(move(new_tree));
			}
		}
	}

	if (best == INT32_MAX)
		return -1;

	return best;
}

#ifdef _DEBUG

#define MAX_N 500000

static int N, K;
static int H[MAX_N][2];
static int L[MAX_N];
static int solution;

inline void my_assert(int e)
{
	if (!e)
		abort();
}

void read_input()
{
	int i;
	my_assert(2 == scanf("%d %d", &N, &K));
	for (i = 0; i < N - 1; i++)
		my_assert(3 == scanf("%d %d %d", &H[i][0], &H[i][1], &L[i]));
	my_assert(1 == scanf("%d", &solution));
}

signed main()
{
	int ans;
	read_input();
	ans = best_path(N, K, H, L);
	if (ans == solution)
		printf("Correct.\n");
	else
		printf("Incorrect. Returned %d, Expected %d.\n", ans, solution);

	return 0;
}

#endif

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57