Submission #875600

#	Time	Username	Problem	Language	Result	Execution time	Memory
875600		aykhn	Race (IOI11_race)	C++17	100 / 100	684 ms	51516 KiB

race

#include "race.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pii;
typedef long double ld;
 
#define pb push_back
#define ins insert
#define fi first
#define se second
#define mod (ll)(1e9 + 7)
#define mxn (ll)(2e5 + 5)
#define inf (ll)(0x3F3F3F3F)

int n, k;
vector<pii> adj[mxn];
int sz[mxn];
int used[mxn];

void getsize(int a, int p)
{
	sz[a] = 1;
	for (pii v : adj[a])
	{
		if (used[v.fi] || v.fi == p) continue;
		getsize(v.fi, a);
		sz[a] += sz[v.fi];
	}
}

int findcent(int a, int p, int curn)
{
	for (pii v : adj[a])
	{
		if (used[v.fi] || v.fi == p) continue;
		if (sz[v.fi] > curn/2) return findcent(v.fi, a, curn);
	}
	return a;
}
vector<pii> arr;
map<int, int> mp;
int res = inf;

void init(int a, int p, int w, int w1)
{
	if (mp.find(k - w) != mp.end())
	{
		res = min(res, mp[k - w] + w1);
	}
	arr.pb({w, w1});
	for (pii v : adj[a])
	{
		if (used[v.fi] || v.fi == p) continue;
		init(v.fi, a, w + v.se, w1 + 1);
	}
}

void maincent(int a)
{
	mp.clear();
	getsize(a, a);
	int c = findcent(a, a, sz[a]);
	mp[0] = 0;
	for (pii v : adj[c])
	{
		if (used[v.fi]) continue;
		arr.clear();
		init(v.fi, c, v.se, 1);
		for (pii x : arr)
		{
			if (mp.find(x.fi) == mp.end()) mp[x.fi] = x.se;
			else mp[x.fi] = min(mp[x.fi], (int)x.se);
		}
	}
	used[c] = 1;
	for (pii v : adj[c])
	{
		if (used[v.fi]) continue;
		maincent(v.fi);
	}

}

int best_path(int N, int K, int H[][2], int L[])
{
	n = N;
	k = K;
	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]});
	}
	maincent(0);
	return (res == inf ? -1 : res);
}

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