Submission #488732

#	Time	Username	Problem	Language	Result	Execution time	Memory
488732		ssense	Race (IOI11_race)	C++14	100 / 100	1143 ms	47528 KiB

race

#include <bits/stdc++.h>
#include "race.h"
typedef long long  ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define nax 200005
#define pb push_back
#define sc second
#define fr first
//#define int long long
//#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
vector<pair<int, ll>> adj[200005];
int n_glob;
int k_glob;
int size_sub[200005];
int del[200005];
 
void calc(int u, int par)
{
	size_sub[u] = 1;
	for(auto v : adj[u])
	{
		if(del[v.fr] == 0 && v.fr != par)
		{
			calc(v.fr, u);
			size_sub[u]+=size_sub[v.fr];
		}
	}
}
 
int find_centroid(int u, int size, int par)
{
	for(auto v : adj[u])
	{
		if(v.fr != par && del[v.fr] == 0 && size_sub[v.fr] > size)
		{
			return find_centroid(v.fr, size, u);
		}
	}
	return u;
}
 
int ans = INT_MAX;
map<ll, int> cnt;

void dfs(int u, int par, ll weight, int type, int depth){
	if(weight > k_glob)return;
	if(type == 0){
		if(cnt.count(k_glob - (int)weight)){
			ans = min(ans, cnt[k_glob - weight] + depth);
		}
	}
	else{
		if(!cnt.count((int)weight))cnt[(int)weight] = depth;
		else cnt[weight] = min(cnt[weight], depth);
	}
 
	for(auto x: adj[u]){
		ll v = x.first, w = x.second;
		if(v == par || del[v])continue;
		dfs((int)v, u, weight + w, type, depth + 1);
	}
}
 
void assign(int u)
{
	calc(u, -1);
	int centroid = find_centroid(u, size_sub[u] / 2, -1);
	del[centroid] = 1;
	cnt.clear();
	cnt[0] = 0;
	for(auto x : adj[centroid])
	{
		if(del[x.fr] == 1)
		{
			continue;
		}
		dfs(x.fr, -1, x.sc, 0, 1);
		dfs(x.fr, -1, x.sc, 1, 1);
	}
	for(auto x : adj[centroid])
	{
		if(del[x.fr] == 0)
		{
			assign(x.fr);
		}
	}
}
 
int best_path(int n, int k, int h[][2],int l[])
{
	ans = INT_MAX;
	n_glob = n;
	k_glob = k;
	for(int i = 0; i <= n; i++)
	{
		adj[i].clear();
		del[i] = 0;
		size_sub[i] = 0;
	}
	cnt.clear();
	for(int i = 0; i < n-1; i++)
	{
		adj[h[i][0]].pb({h[i][1], l[i]});
		adj[h[i][1]].pb({h[i][0], l[i]});
	}
	assign(0);
	if(ans == INT_MAX)
	{
		return -1;
	}
	return ans;
}
/*
int32_t main(){
	int n, k;
	cin >> n >> k;
	int h[n-1][2], l[n-1];
	for(int i = 0; i < n-1; i++)
	{
		cin >> h[i][0] >> h[i][1];
	}
	for(int i = 0; i < n-1; i++)
	{
		cin >> l[i];
	}
	cout << best_path(n, k, h, l) << endl;
}
 */
/*
3 3
0 1
0 2
1 1
 
4 3
0 1
1 2
1 3
1 2 4
 
11 12
0 1
0 2
2 3
3 4
4 5
0 6
6 7
6 8
8 9
8 10
3 4 5 4 6 3 2 5 6 7
 */

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