Submission #1209249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209249		vache_kocharyan	Race (IOI11_race)	C++17	0 / 100	0 ms	320 KiB

race

//#include "race.h"
#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

vector<vector<pair<int, int>>>G;
int answ = 1e9 + 7, compSize, maxDep, maxMaxDep;
const int NN = 2e5 + 5;
map<int, int>depth, cur_depth;
bool used[NN];
int sz[NN];
int k;

void dfs(int node, int parent)
{
	sz[node] = 1;
	for (auto i : G[node])
	{
		if (i.first == parent || used[i.first])
			continue;
		dfs(i.first, node);
		sz[node] += sz[i.first];
	}
}

int find_centroid(int node, int parent)
{
	for (auto i : G[node])
	{
		if (i.first == parent || used[i.first])
			continue;
		if (sz[i.first] * 2 >= compSize)
			return find_centroid(i.first, node);
	}
	return node;
}

int centroid(int u)
{
	dfs(u, -1);
	compSize = sz[u];
	return find_centroid(u, -1);
}

void solve(int node, int parent, int node_depth, int node_sum)
{
	if (cur_depth.count(node_sum))
		cur_depth[node_sum] = min(cur_depth[node_sum], node_depth);
	else
		cur_depth[node_sum] = node_depth;

	if (depth.count(k - node_sum))
		answ = min(answ, node_depth + depth[k - node_sum]);

	for (auto i : G[node])
	{
		if (i.first == parent || used[i.first])
			continue;
		solve(i.first, node, node_depth + 1, node_sum + i.second);
		if (parent != -1)
			continue;
		for (auto &it : cur_depth)
		{
			if (depth.count(it.first))
				depth[it.first] = it.second;
			else
				depth[it.first] = min(depth[it.first], it.second);
			it.second = 0;
		}
		cur_depth.clear();
		//assert(!cur_depth.empty());
	}
}

void centroid_decomposition()
{
	queue<int>q;
	q.push(0);
	while (!q.empty())
	{
		int u = q.front();
		q.pop();

		int c = centroid(u);
		solve(c, -1, 0, 0);
		depth.clear();
		//assert(!depth.empty());
		used[c] = true;
		for (auto i : G[c])
		{
			if (used[i.first])
				continue;
			q.push(i.first);
		}
	}
}

int best_path(int N, int K, int H[][2], int L[])
{
	k = K;
	G.resize(N + 1);
	for (int i = 0; i < N - 1; i++)
	{
		G[H[i][0]].push_back({ H[i][1], L[i] });
		G[H[i][1]].push_back({ H[i][0], L[i] });
	}
	centroid_decomposition();
	if (answ == 1e9 + 7)
		return -1;
	return answ;
}

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