Submission #936993

#	Time	Username	Problem	Language	Result	Execution time	Memory
936993		vjudge1	Race (IOI11_race)	C++17	0 / 100	3 ms	9560 KiB

race

//starting with the name of almighty ALLAH
// Practice is the only shortcut to improve
#include<bits/stdc++.h>
#include "race.h"
#define ll long long
#define pb push_back
#define vc vector
#define vi vc<int>
#define vl vc<ll>
#define mp(x,y) make_pair(x,y)
#define yes cout<<"YES"<<'\n';
#define no cout<<"NO"<<'\n';
#define tst int t;cin>>t;while(t--)
#define srt(v) sort(v.begin(),v.end());
#define rsrt(v) sort(v.rbegin(),v.rend());
#define rj ios::sync_with_stdio(false);cin.tie(0);
#define rvs(v) reverse(v.begin(),v.end());
#define F first
#define S second
#define MOD 1000000007
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*b)/gcd(a,b)
#define PI 2*acos(0.0)
#define pii pair<int,int>
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define coutv(v) for(auto it:v)cout<<it<<' ';cout<<endl;
#define cinv(v) for(auto &it:v)cin>>it;
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define ld long double
#define nl '\n'
using namespace std;
/* #ifndef ONLINE_JUDGE
#include "algo/debug.h"
#else
#define dbg(x...)
#endif */
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int my_rand(int l, int r)
{
	return uniform_int_distribution<int>(l, r) (rng);
}
const int N = 2e5 + 2;
vector<pii>adj[N];
int a, b;
bool done[N];
int sz[N];
int cur_subtree_size;
void set_subtree_size(int n, int p)
{
	sz[n] = 1;
	cur_subtree_size++;
	for (auto it : adj[n])
	{
		if (it.F == p || done[it.first])
			continue;
		set_subtree_size(it.F, n);
		sz[n] += sz[it.first];
	}
}
int get_centroid(int n, int p)
{
	for (auto it : adj[n])
	{
		if (it.first == p || done[it.first])
			continue;
		if (sz[it.first] > cur_subtree_size / 2)
			return get_centroid(it.first, n);
	}
	return n;
}
int an;
map<int, int>save;
void dfs(int n, int p, int lvl, int q, int lv = 1)
{
	if (lvl > b)
		return;
	if (q)
	{
		if (save.find(b - lvl) != save.end())
		{
			an = min(an, lv + save[b - lvl]);
			return;
		}
	}
	else {
		if (save.find(lvl) != save.end())
		{
			save[lvl] = min(save[lvl], lv);
		}
		else
			save[lvl] = lv;
	}
	for (auto it : adj[n])
	{
		if (it.first == p or done[it.first])
			continue;
		dfs(it.first, n, lvl + it.second, q, lv + 1);
	}
}
void decompose(int n)
{
	cur_subtree_size = 0;
	set_subtree_size(n, n);
	int centroid = get_centroid(n, n);
	save[0] = 0;
	for (auto it : adj[n])
	{
		if (!done[it.first])
		{
			dfs(it.first, centroid, 0, 1);
			dfs(it.first, centroid, 0, 0);
		}
	}
	save.clear();
	done[centroid] = 1;
	for (auto it : adj[centroid])
	{
		if (done[it.first])
			continue;
		decompose(it.first);
	}
}
int best_path(int N, int K, int H[][2], int L[])
{
	for (int i = 0; i < N - 1; i++)
	{
		adj[H[i][0]].push_back({H[i][1], L[i]});
		adj[H[i][1]].push_back({H[i][0], L[i]});
	}
	a = N;
	b = K;
	an = INT_MAX;
	decompose(0);
	if (an == INT_MAX)
		an = -1;
	return an;
}

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