Submission #166020

#	Time	Username	Problem	Language	Result	Execution time	Memory
166020		JustInCase	Race (IOI11_race)	C++17	31 / 100	353 ms	30812 KiB

race

#include <iostream>
#include <vector>
#include <cstring>

const int32_t MAX_N = 2e5;

#ifdef LOCAL
	#include "grader.cpp"
#endif
#ifndef LOCAL
	#include "race.h"
#endif

struct Vertex {
	bool solved;
	int32_t subtree;
	std::vector< std::pair< int32_t, int32_t > > v;
};

int32_t k, ans = -1, dists[MAX_N + 5];
Vertex g[MAX_N + 5];

void dfs_subtree(int32_t u, int32_t par) {
	g[u].subtree = 1;
	for(auto &e : g[u].v) {
		auto v = e.first;
		if(!g[v].solved && v != par) {
			dfs_subtree(v, u);
			g[u].subtree += g[v].subtree;
		}
	}
}

int32_t dfs_centroid(int32_t u, int32_t par, int32_t subtree) {
	for(auto &e : g[u].v) {
		auto v = e.first;
		if(!g[v].solved && v != par && g[v].subtree > subtree / 2) {
			return dfs_centroid(v, u, subtree);
		}
	}

	return u;
}

void dfs_ans(int32_t u, int32_t par, int32_t d, int32_t cntEdges) {
	if(d > k) {
		return;
	}

	if(dists[k - d] != -1) {
		if(ans == -1 || ans > cntEdges + dists[k - d]) {
			ans = cntEdges + dists[k - d];
		}
	}

	for(auto &e : g[u].v) {
		auto v = e.first;
		auto w = e.second;

		if(!g[v].solved && v != par) {
			dfs_ans(v, u, d + w, cntEdges + 1);
		}
	}
}

void dfs_add(int32_t u, int32_t par, int32_t d, int32_t cntEdges) {
	if(d > k) {
		return;
	}

	if(dists[d] == -1 || dists[d] > cntEdges) {
		dists[d] = cntEdges;
	}

	for(auto &e : g[u].v) {
		auto v = e.first;
		auto w = e.second;

		if(!g[v].solved && v != par) {
			dfs_add(v, u, d + w, cntEdges + 1);
		}
	}
}

void dfs_clear(int32_t u, int32_t par, int32_t d) {
	if(d > k) {
		return;
	}
	dists[d] = -1;

	for(auto &e : g[u].v) {
		auto v = e.first;
		auto w = e.second;

		if(!g[v].solved && v != par) {
			dfs_clear(v, u, d + w);
		}
	}
}

void solve(int32_t u) {
	dfs_subtree(u, -1);
	int32_t centroid = dfs_centroid(u, -1, g[u].subtree);
	
	dists[0] = 0;
	for(auto &e : g[centroid].v) {
		auto v = e.first;

		if(!g[v].solved) {
			dfs_ans(v, centroid, e.second, 1);
			dfs_add(v, centroid, e.second, 1);
		}
	}

	dfs_clear(centroid, -1, 0);
	g[centroid].solved = true;
	
	for(auto &e : g[centroid].v) {
		auto v = e.first;
		
		if(!g[v].solved) {
			solve(v);
		}
	}
}

int32_t best_path(int32_t n, int32_t _k, int32_t h[][2], int32_t l[]) {
	k = _k;
	for(int32_t i = 0; i < n - 1; i++) {
		g[h[i][0]].v.push_back({ h[i][1], l[i] });
		g[h[i][1]].v.push_back({ h[i][0], l[i] });
	}
	
	memset(dists, -1, sizeof(dists));
	solve(1);

	return ans;
}

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