Submission #836849

#	Time	Username	Problem	Language	Result	Execution time	Memory
836849		Elias	Race (IOI11_race)	C++17	43 / 100	3082 ms	34584 KiB

race

#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#endif

#include <bits/stdc++.h>

using namespace std;

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

vector<vector<pair<int, int>>> adj;
vector<int> 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, vector<pair<int, int>> &out, int d = 0, int depth = 0, int p = -1)
	{
		out.push_back({d, depth});

		for (auto [c, D] : adj[i])
		{
			if (c != p && !blocked[c])
			{
				dfs(c, out, d + D, depth + 1, i);
			}
		}
	}
	vector<int> split()
	{
		if (centroid == -1)
			return {};
		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);

		if (n <= 1)
			return;

		find_centroid(start);

		assert(centroid != -1);

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

		for (auto [c, d] : adj[centroid])
		{
			vector<pair<int, int>> blub;
			dfs(c, blub, d, 1, centroid);

			for (auto &[a, b] : blub)
			{
				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 : blub)
				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<int> todo = {0};

	while (todo.size()) {
		int i = todo.back();
		todo.pop_back();

		auto tree = Tree(i);

		for (int x : tree.split())
			todo.push_back(x);
	}

	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()
{
	freopen("/home/elias/Downloads/ioi2011tests/race-test/subtask4/grader.in.5", "r", stdin);

	cin.tie(0);
	ios_base::sync_with_stdio(false);

	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: 22 / 22
• Subtask 4: 0 / 57