Submission #1209214

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

race

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

using namespace std;

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

void merge_(set<int>&a, set<int>b)
{
	for (auto i : b)
		a.insert(i);
}

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 (node_sum > k)
		return;
	if (node_sum == k)
	{
		answ++;
		return;
	}

	cur_depth[node_sum].insert(node_depth);
	if (!depth[k - node_sum].empty())
	{
		answ = min(answ, node_depth + *depth[k - node_sum].begin());
	}
	

	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)
		{
			merge_(depth[it.first], it.second);
			it.second.clear();
		}
	}
}

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();
		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)
		return -1;
	return answ;
}

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