Submission #385127

#	Time	Username	Problem	Language	Result	Execution time	Memory
385127		hivakarami	Race (IOI11_race)	C++14	21 / 100	425 ms	19308 KiB

race

#include "race.h"
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
typedef long double ld;
#define f first
#define s second
 
const int N = 1e5 + 100;
const int lg = 18;
const int inf = 1e9 + 10;

int ans = inf, W[N], w[N];
int n, k, h[N], par[N], sz[N];
vector<int> v, vec;
vector<pair<int, int>> adj[N];
map<ll, int> mn;
bool dead[N];


void DFS(int u)
{
	v.push_back(u);
	for(auto it : adj[u])
	{
		int x = it.f;
		if(!dead[x] && x != par[u])
			DFS(x);
	}
}

void dfs(int u)
{
	sz[u] = 1;
	vec.push_back(u);
	for(auto it : adj[u])
	{
		int x = it.f, id = it.s;
		if(!dead[x] && x != par[u])
		{
			par[x] = u;
			h[x] = h[u] + 1;
			W[x] = W[u] + w[id];
			dfs(x);
			sz[u] += sz[x];
		}
	}
}


inline void cl()
{
	for(auto u : vec)
	{
		par[u] = -1;
		sz[u] = h[u] = W[u] = 0;
	}
	vec.clear();
}


int centroid(int u)
{
	for(auto it : adj[u])
	{
		int x = it.f;
		if(!dead[x] && x != par[u] && sz[x] > int(vec.size())/2)
			return centroid(x);
	}
	return u;
}


void solve(int u)
{
	cl();
	dfs(u);
	u = centroid(u);
	cl();
	dfs(u);
	//cout << ".." << u << ' ' << vec.size() << endl;
	mn.clear();
	dead[u] = true;
	
	for(auto it : adj[u])
	{
		int x = it.f;

		if(dead[x])
			continue;
			
		v.clear();
		DFS(x);
		
		//cout << "X" << x << endl;
		
		for(auto y : v)
		{
			//cout << y << endl;
			if(k >= W[y] && mn.find(k - W[y]) != mn.end())
			{
				ans = min(ans, h[y] + mn[k - W[y]]);
				//cout << x << ' ' << y << ' ' << h[y] << ' ' << k - W[y] << ' ' << mn[k - W[y]] << endl;
			}
		}
		
		for(auto y : v)
		{
			if(mn.find(W[y]) != mn.end())
				mn[W[y]] = min(mn[W[y]], h[y]);
			else
				mn[W[y]] = h[y];
		}
	}
	
	if(mn.find(k) != mn.end())
	{
		ans = min(ans, mn[k]);
		//cout << "mn[k]" << mn[k] << endl;
	}
	
	
	for(auto it : adj[u])
	{
		int x = it.f;
		if(!dead[x])
			solve(x);
	}
	
	
	
}




//*

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 x = H[i][0], y = H[i][1];
		adj[x].push_back({y, i});
		adj[y].push_back({x, i});
	}	
	for(int i = 0; i < n-1; i++)
		w[i] = L[i];
	
	
	solve(0);

	if(ans >= inf)
		ans = -1;
	
	return ans;
	
}

//*/







/*
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);	

	cin >> n >> k;
	
	for(int i = 0; i < n-1; i++)
	{
		int x, y;
		cin >> x >> y;
		adj[x].push_back({y, i});
		adj[y].push_back({x, i});
	}	
	for(int i = 0; i < n-1; i++)
		cin >> w[i];
	
	
	solve(0);
	
	if(ans == inf)
		ans = -1;
	
	cout << ans << endl;

	return 0;
	
}

//*/

 
/*
3 2
0 1
1 2
1 1
*/ 

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