Submission #887523

#	Time	Username	Problem	Language	Result	Execution time	Memory
887523		BBart888	Race (IOI11_race)	C++14	0 / 100	2 ms	9760 KiB

race

#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <queue>
#include <stack>
#include <cassert>
#include <cstring>
#include <climits>
#include <functional>
#include<cstdlib>
//#include "arc.h"
//#include "dreaming.h"


using namespace std;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long LL;



const int MAXN = 2e5 + 11; 
using ll = long long;
const ll mod1 = 1e9 + 7;
const ll mod2 = 1000000021;
const ll P = 31;



/*
void setIO(string name = "") {
	cin.tie(0)->sync_with_stdio(0); // see /general/fast-io
	if ((name.size())) {
		freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
		freopen((name + ".out").c_str(), "w", stdout);
	}
}
*/



vector<pair<int,ll>> adj[MAXN];
ll n, k;
int sz[MAXN];
bool vis[MAXN];
map<ll, ll> mp;
vector<ll> to_del;
map<ll, bool> used;
ll ans = 1e9;

void dfs(int v, int p,bool fill,ll sum,ll len)
{
	if (sum > k)
		return;
	if (fill)
	{
		to_del.push_back(sum);
		if (used[sum] == 0)
			mp[sum] = len, used[sum] = true;
		else
			mp[sum] = min(mp[sum], len);
	}
	else
	{ 
		ll need = k - sum;
		//cout << v << " " << sum << " " << len << 
		//	" and " << need << " " << mp[need] << '\n';
		if (need == 0 || mp[need] != 0)
			ans = min(ans, mp[need] + len);
	}

	for (auto u : adj[v])
	{
		if (u.first == p || vis[u.first])
			continue;
		dfs(u.first, v, fill, sum + u.second, len + 1);
	}

}





int find_size(int v, int p)
{
	if (vis[v])
		return 0;
	sz[v] = 1;
	for (auto u : adj[v])
	{
		if (u.first == p)
			continue;
		sz[v] += find_size(u.first, v);
	}
	return sz[v];
}


int find_centroid(int v, int  p,int n)
{
	for (auto u : adj[v])
	{
		if (u.first == p || vis[u.first])
			continue;
		if (sz[u.first] > n / 2)
			return find_centroid(u.first, v, n);
	}
	return v;
}



void decomp(int v, int p)
{
	find_size(v, -1);

	int c = find_centroid(v, -1, sz[v]);

	vis[c] = true;

	to_del.clear();
	for (auto u : adj[c])
	{
		if (vis[u.first])
			continue;
		dfs(u.first, -1, 0, u.second, 1);
		dfs(u.first, -1, 1, u.second, 1);
	}
	

	for (auto vals : to_del)
	{
		mp[vals] = 0;
		used[vals] = false;
	}

	for (auto u : adj[c])
	{
		if (vis[u.first])
			continue;
		decomp(u.first, c);
	}
}



int best_path(int _n, int _k, int h[][2], int l[])
{
	for (int i = 0; i < n - 1; i++)
	{
		int v = h[i][0]+1;
		int u = h[i][1]+1;
		int cost = l[i];
		adj[u].push_back({ v,cost });
		adj[v].push_back({ u,cost });
	}


	n = _n;
	k = _k;


	decomp(1, -1);
	

	return ans;

}




/*

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);
	//setIO("movie");
	
	cin >> n >> k;
	for(int i =1;i<n;i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back({ b,c });
		adj[b].push_back({ a,c });
	}
	
	decomp(1, -1);
	if (ans == 1e9)
		cout << -1 << '\n';
	else
		cout << ans << '\n';


	

	return 0;
}






*/

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