Submission #943489

#	Time	Username	Problem	Language	Result	Execution time	Memory
943489		SoSmolSten	Race (IOI11_race)	C++17	100 / 100	261 ms	36944 KiB

race

#include <bits/stdc++.h>
#include "race.h"
#define pp pair<int, int>
#define F first
#define S second
using namespace std;
const int SZ = 2e5 + 10, M = 1e6 + 10, INF = 1e9;
vector<pp> graph[SZ];
int mn[M], ti[M], c[SZ], n, k, ans = INF, cnt = 0;
bool del[SZ];

void dfs(int u, int p){
	c[u] = 1;
	for(auto &[v, w] : graph[u]){
		if(v == p || del[v]) continue;
		dfs(v, u);
		c[u] += c[v];
	}
}

void upd(int u, int p, int w, int d){
	if(w > k) return; 
	if(ti[w] != cnt) mn[w] = d;
	else mn[w] = min(mn[w], d);
	ti[w] = cnt;
	
	for(auto &[v, l] : graph[u]){
		if(v == p || del[v]) continue;
		upd(v, u, w + l, d + 1);
	}
}

void calc(int u, int p, int w, int d){
	if(w > k) return;
	if(ti[k - w] == cnt) ans = min(ans, mn[k - w] + d);

	for(auto &[v, l] : graph[u]){
		if(v == p || del[v]) continue;
		calc(v, u, w + l, d + 1);
	}
}

int centroid(int u, int p, int sz) {
	for(auto &[v, _] : graph[u]){
		if(v == p || del[v]) continue;
		if (c[v] > (sz >> 1)) return centroid(v, u, sz);
	}
	return u;
}

void solve(int u){
	dfs(u, 0);
	u = centroid(u, 0, c[u]);
	del[u] = 1;
	ti[0] = ++cnt;
	for(auto &[v, w] : graph[u]){
		if(del[v]) continue;
		calc(v, u, w, 1);
		upd(v, u, w, 1);
	}
	for(auto &[v, _] : graph[u]){
		if(!del[v]) solve(v);
	}
}

int best_path(int N, int K, int H[][2], int L[]){
	n = N, k = K;
	for(int i = 1, u, v, w; i < n; ++i){
		u = H[i - 1][0] + 1;
		v = H[i - 1][1] + 1;
		w = L[i - 1];
		graph[u].push_back({v, w});
		graph[v].push_back({u, w});
	}
	fill(mn, mn + M - 5, INF);
	mn[0] = 0;
	solve(1);
	if(ans == INF) return -1;
  	return ans;
}

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