Submission #1105633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105633		anngela	Race (IOI11_race)	C++17	100 / 100	228 ms	38364 KiB

race

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
 
const int N = 2e5+5, W = 1e6+5, inf = 1e9;
 
int n, k, sz[N];
int hmin[W], ans;
bool del[N];
vector<pair<int,int>> adj[N];
 
int Size(int x, int t)
{
	sz[x] = 1;
	for (auto [y, _] : adj[x])
	{
		if (y == t || del[y]) continue;
		sz[x] += Size(y, x);
	}
	return sz[x];
}
 
int Centroid(int x, int size, int t = -1)
{
	for (auto [y, _] : adj[x])
	{
		if (y == t || del[y]) continue;
		if (2 * sz[y] > size)
			return Centroid(y, size, x);
	}
	return x;
}
 
queue<int> q;
stack<pair<int, int>> path;
 
void dfs(int x, int t, int we = 0, int d = 0)
{
	if (hmin[k - we] != inf)
		ans = min(ans, hmin[k - we] + d);
	
	for (auto [y, w] : adj[x])
	{
		if (del[y] || y == t) continue;
 
		if (we + w <= k && d + 1 <= ans) 
			dfs(y, x, we + w, d + 1);
		if (t == -1)
		{
			while (!path.empty())
			{
				auto [dist, h] = path.top(); 
				path.pop();
				hmin[dist] = min(hmin[dist], h);
			}
		}
	}
	
	if (t != -1)
	{
		q.push(we);
		path.emplace(we, d);
	}
	else
	{
		while (!q.empty())
		{
			int dist = q.front(); 
			q.pop();
			hmin[dist] = inf;
		}
	}
}
 
void Decompose(int x)
{
	x = Centroid(x, Size(x, -1));
	del[x] = true;
 
	dfs(x, -1);
 
	for (auto e : adj[x])
	{
		int y = e.fi;
		if(!del[y]) Decompose(y);
	}
}
 
int best_path(int N, int K, int H[][2], int L[])
{
	n = N, k = K;
	for (int i = 0; i < n-1; i++)
	{
		int u = H[i][0] + 1, v = H[i][1] + 1, w = L[i];
		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);
	}
 
	ans = inf;
	for(int i = 1; i <= k; i++){
		hmin[i] = inf;
	}
	Decompose(1);
	return (ans == inf ? -1 : ans);
}

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