Submission #836783

#	Time	Username	Problem	Language	Result	Execution time	Memory
836783		Elias	Race (IOI11_race)	C++17	21 / 100	3063 ms	33828 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;

	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_size;
	}

	void dfs(int i, multiset<pair<int, int>>& out, int d = 0, int depth = 0, int p = -1)
	{
		out.insert({d, depth});

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

	}
	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<multiset<pair<int, int>>> separate;

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

		multiset<pair<int, int>> all;
		all.insert({0, 0});


		for (auto &child : separate)
		{
			for (auto &[a, b] : child)
			{
				int other = k - a;

				auto ptr = all.lower_bound({other, 0});
				if (ptr != all.end() && ptr->first == other) {
					int new_one = b + ptr->second;
					best = min(best, new_one);
				}
			}

				for (auto x : child)
					all.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