Submission #351159

#	Time	Username	Problem	Language	Result	Execution time	Memory
351159		Kenzo_1114	Race (IOI11_race)	C++17	0 / 100	6 ms	9708 KiB

race

#include<bits/stdc++.h>
#include "race.h"
using namespace std;
const int MAXN = 200010;
const int MAXK = 1000010;

int n, k, n_cur, sub[MAXN], best[MAXK], ans = MAXK;
vector<int> graph[MAXN], cost[MAXN];
bool marc[MAXN];

void find_sub(int v, int p)
{
	sub[v] = 1;
	for(int i = 0; i < (int) graph[v].size(); i++)
	{
		int u = graph[v][i];
		if(u == p || marc[u])	continue;
		find_sub(u, v), sub[v] += sub[u];	
	}
}

int find_centroid(int v, int p)
{
	for(int i = 0; i < (int) graph[v].size(); i++)
	{
		int u = graph[v][i];
		if(u == p || marc[u])	continue;
		if(2 * sub[u] >= n_cur)	return find_centroid(u, v);
	}

	return v;
}

void dfs(int v, int p, int dist, int depth, bool flag)
{	
	if(k < dist)	return;

	if(flag)	
	{
		if(best[dist] == 0)	best[dist] = depth;
		else	best[dist] = min(best[dist], depth);	
	}
	else		best[dist] = 0;

	for(int i = 0; i < (int) graph[v].size(); i++)
	{
		int u = graph[v][i];
		int c = cost[v][i];

		if(u != p && !marc[u])	dfs(u, v, dist + c, depth + 1, flag);
	}
}

void dfs2(int v, int p, int dist, int depth)
{
	if(k < dist)	return;

	if(best[k - dist])	ans = min(ans, best[k - dist] + depth);
	if(dist == k)	ans = min(ans, depth);

	for(int i = 0; i < (int) graph[v].size(); i++)
	{
		int u = graph[v][i];
		int c = graph[v][i];

		if(u != p && !marc[u]) dfs2(u, v, dist + c, depth + 1);
	}
}

void decompose(int v, int p)
{
	find_sub(v, p);
	n_cur = sub[v];
	int c = find_centroid(v, p);

//	printf("\nc = %d\n", c - 1);
	marc[c] = true;

	for(int i = 0; i < (int) graph[c].size(); i++)
	{
		int u = graph[c][i];

		if(u == p || marc[u])	continue;

		dfs2(u, c, cost[c][i], 1);
		dfs(u, c, cost[c][i], 1, true);
	}

//	for(int i = 0; i <= k; i++)	printf("best[%d] = %d\n", i, best[i]);

	dfs(c, c, 0, 0, false);

	for(int i = 0; i < (int) graph[c].size(); i++)
	{
		int u = graph[c][i];
		if(!marc[u])	decompose(u, c);
	}
}

int best_path(int N, int K, int h[][2], int l[])
{
	n = N, k = K;
	for(int i = 0; i < n - 1; i++)
	{
		int u = h[i][0] + 1;
		int v = h[i][1] + 1;
		int w = l[i];

		graph[u].push_back(v);
		graph[v].push_back(u);
		cost[u].push_back(w);
		cost[v].push_back(w);
	}

	decompose(1, 1);

	return (ans == MAXK) ? -1 : ans;
}

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