Submission #210546

#	Time	Username	Problem	Language	Result	Execution time	Memory
210546		faremy	Race (IOI11_race)	C++14	100 / 100	813 ms	33272 KiB

race

#include "race.h"

#include <vector>
#include <algorithm>


struct Edge
{
	Edge(int v, int w) : dest(v), weight(w) {}
	int dest, weight;
};

const int MAXN = 2e5;
const int MAXK = 1e6 + 1;

std::vector<Edge> tree[MAXN];
bool seen[MAXN];
int treeSize[MAXN];
int minRoad[MAXK];


int calcsize(int node)
{
	if (seen[node])
		return 0;
	seen[node] = true;
	treeSize[node] = 1;

	for (Edge &edge : tree[node])
		treeSize[node] += calcsize(edge.dest);
	seen[node] = false;
	return treeSize[node];
}

int findcentr(int node, int tsize)
{
	seen[node] = true;
	int maxSub = tsize - treeSize[node];	

	for (Edge &edge : tree[node])
		if (!seen[edge.dest])
		{
			int centr = findcentr(edge.dest, tsize);
			if (centr != -1)
			{
				seen[node] = false;
				return centr;
			}

			maxSub = std::max(maxSub, treeSize[edge.dest]);
		}

	seen[node] = false;
	if (maxSub > tsize / 2)
		return -1;
	return node;
}

int count(int node, int taken, int dist, int wanted)
{
	if (seen[node] || dist > wanted)
		return MAXN;
	seen[node] = true;
	int length = taken + minRoad[wanted - dist];

	for (Edge &edge : tree[node])
		length = std::min(length, count(edge.dest, taken + 1, dist + edge.weight, wanted));
	seen[node] = false;
	return length;
}

void mark(int node, int taken, int dist, int wanted)
{
	if (seen[node] || dist > wanted)
		return;
	seen[node] = true;
	minRoad[dist] = std::min(minRoad[dist], taken);

	for (Edge &edge : tree[node])
		mark(edge.dest, taken + 1, dist + edge.weight, wanted);
	seen[node] = false;
}

void unmark(int node, int taken, int dist, int wanted)
{
	if (seen[node] || dist > wanted)
		return;
	seen[node] = true;
	minRoad[dist] = MAXN;

	for (Edge &edge : tree[node])
		unmark(edge.dest, taken + 1, dist + edge.weight, wanted);
	seen[node] = false;
}

int findpath(int node, int wanted)
{
	if (seen[node])
		return MAXN;
	int s = calcsize(node);
	int centroid = findcentr(node, s);
	seen[centroid] = true;

	int length = MAXN;
	minRoad[0] = 0;

	for (Edge &edge : tree[centroid])
	{
		length = std::min(length, count(edge.dest, 1, edge.weight, wanted));
		mark(edge.dest, 1, edge.weight, wanted);
	}

	for (Edge &edge : tree[centroid])
		unmark(edge.dest, 1, edge.weight, wanted);
	for (Edge &edge : tree[centroid])
		length = std::min(length, findpath(edge.dest, wanted));
	return length;
}

int best_path(int N, int K, int H[][2], int L[])
{
	for (int iEdge = 0; iEdge < N - 1; iEdge++)
	{
		tree[H[iEdge][0]].emplace_back(H[iEdge][1], L[iEdge]);
		tree[H[iEdge][1]].emplace_back(H[iEdge][0], L[iEdge]);
	}

	std::fill_n(minRoad, K + 1, MAXN);
	int length = findpath(0, K);

	if (length == MAXN)
		return -1;
	return length;
}

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