Submission #384855

#	Time	Username	Problem	Language	Result	Execution time	Memory
384855		ace_in_the_hole	Race (IOI11_race)	C++14	21 / 100	3093 ms	27372 KiB

race

#include "race.h"

#include<bits/stdc++.h>
using namespace std;

#define push_back emplace_back

typedef long long Int;
typedef long double Real;

const int MOD = 2004010501;//>2e9
const int INF = 1e9;

const int MAXN = 2e5 + 500;
int num_nodes, capa;

typedef pair<int,int> Edge;
vector<Edge> graph[MAXN];
vector<int> adj[MAXN];

bool cut[MAXN];

int cnt[MAXN], par[MAXN];
void get_force(int u) {
	cnt[u] = 1;
	for (int v : adj[u]) 
		if (v != par[u] and !cut[v]) 
			par[v] = u,
			get_force(v), cnt[u] += cnt[v];
}

int answer = INF;

const int MAXV = 1e6 + 500;
int best[MAXV], weight[MAXN], depth[MAXN];
int upd_list[MAXN], ptL, ptR;

void find_path(int u, int pa) {
	if (weight[u] > capa) return ;
	
	for (auto e : graph[u]) {
		const int& v = e.first;
		if (v == pa or cut[v]) continue;
		weight[v] = weight[u] + e.second;
		depth[v] = depth[u] + 1;
		find_path(v, u);
	}
	
//	if (best[capa - weight[u]] + depth[u] < answer) {
//		cerr << "(" << u << ',' << depth[u] << ") with " << best[capa - weight[u]] << '\n';
//	}
	answer = min(answer, best[capa - weight[u]] + depth[u]);
	upd_list[++ptR] = u;
}

void centroid_decomp(int u) {
//	cerr << "In subtree ROOT " << u << '\n';
//	fill(cnt, cnt + 1 + MAXN, 0);
	const int root = u;
	get_force(root);
//	cerr << "Force = " << cnt[u] << '\n';
	int cand; do {
		cand = -1;
		for (int v : adj[u]) 
			if (!cut[v]) {
				int count_sub = (v == par[u]) ? (cnt[root] - cnt[u]) : cnt[v];
				if (count_sub > cnt[root] / 2) 
					{ cand = v; break; }
			}
		if (cand != -1) u = cand; else break;
	} while (true);
	
//	cerr << "CENTROID = " << u << '\n'; 
	cut[u] = true;
	
	ptL = 1; ptR = 0;
	for (auto e : graph[u]) {
		const int& v = e.first;		
//		cerr << "BRANCH " << v << '\n';
		weight[v] = e.second, depth[v] = 1,
		find_path(v, u);
		for (; ptL <= ptR; ) {
			int x = upd_list[ptL++];
			best[weight[x]] = min(best[weight[x]], depth[x]);
		} 
	}
	
	//reset
	for (int x,i = 1; i <= ptR; i++) 
		x = upd_list[i], best[weight[x]] = INF;
//	cerr << " -> " << answer << '\n';
	
	//recursion
	for (int v : adj[u]) 
		if (!cut[v]) centroid_decomp(v);
}

int best_path(int N, int K, int H[][2], int L[])
{
	num_nodes = N;
	capa = K;
	for (int u, v, w, i = 0; i < num_nodes - 1; i++) {
		cin >> u >> v >> w;
		u = H[i][0], v = H[i][1], w = L[i];
		adj[u].push_back(v), 
		adj[v].push_back(u);
		graph[u].push_back(Edge(v, w)),
		graph[v].push_back(Edge(u, w));
	}
	
	fill(best + 1, best + MAXV, INF);
	
	centroid_decomp(0);
	
	if (answer == INF) answer = -1;
	return answer;
}

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