Submission #807479

#	Time	Username	Problem	Language	Result	Execution time	Memory
807479		OrazB	Race (IOI11_race)	C++14	100 / 100	448 ms	50852 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <ll, int>
#define pb push_back
#define ff first
#define ss second

const int N = 2e5+5;
const int MAXN = 1e6+5;
const int inf = 1e9;
int P[MAXN];
int sub[N], rem[N], tp[N], dpt[N];
ll w[N];
int answer = inf;
vector<pii> E[N], G[N];
vector<int> nodes;

void solve(vector<int> nodes, int T, int K){
	for (auto i : nodes){
		G[tp[i]].pb({w[i], dpt[i]});
	}
	for (int i = 1; i <= T; i++){
		for (auto j : G[i]){
			if (j.ff <= K)
				answer = min(answer, P[K-j.ff]+j.ss);
		}
		for (auto j : G[i]){
			if (j.ff <= K) P[j.ff] = min(P[j.ff], j.ss);
		}
		G[i].clear();
	}
	for (auto i : nodes) if (w[i] <= K) P[w[i]] = inf;
}

void dfs(int nd, int pr){
	sub[nd] = 1;
	for (auto i : E[nd]){
		if (i.ff == pr or rem[i.ff]) continue;
		dfs(i.ff, nd);
		sub[nd] += sub[i.ff];
	}
}

int centroid(int nd, int pr, int sz){
	for (auto i : E[nd]){
		if (i.ff == pr or rem[i.ff]) continue;
		if (sub[i.ff]*2 > sz) return centroid(i.ff, nd, sz);
	}
	return nd;
}

void F(int nd, int pr, ll W, int lvl, int T){
	nodes.pb(nd);
	w[nd] = W;
	dpt[nd] = lvl;
	tp[nd] = T;
	for (auto i : E[nd]){
		if (i.ff == pr or rem[i.ff]) continue;
		F(i.ff, nd, W+i.ss, lvl+1, T);
	}
}

void build(int nd, int pr, int K){
	int centr = centroid(nd, 0, sub[nd]);
	rem[centr] = 1;
	nodes.clear();
	int T = 0;
	for (auto i : E[centr]){
		if (rem[i.ff]) continue;
		F(i.ff, 0, i.ss, 1, ++T);
	}
	solve(nodes, T, K);
	for (auto i : E[centr]){
		if (rem[i.ff]) continue;
		dfs(i.ff, 0);
		build(i.ff, centr, K);
	}
}

int best_path(int n, int k, int H[][2], int L[]){
	for (int i = 0; i < n-1; i++){
		E[H[i][0]+1].pb({H[i][1]+1, L[i]});
		E[H[i][1]+1].pb({H[i][0]+1, L[i]});
	}
	P[0] = 0;
	for (int i = 1; i <= k; i++) P[i] = inf+7;
	dfs(1, 0);
	build(1, 0, k);
	if (answer > n) answer = -1;
	return answer;
}


// int main ()
// {
// 	ios::sync_with_stdio(false);
// 	cin.tie(0);
// 	int n, k;
// 	cin >> n >> k;
// 	int H[n][2], L[n];
// 	for (int i = 0; i < n-1; i++){
// 		cin >> H[i][0] >> H[i][1] >> L[i];
// 	}
// 	cout << best_path(n, k, H, L);
// }	

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