Submission #384071

#	Time	Username	Problem	Language	Result	Execution time	Memory
384071		Drew_	Race (IOI11_race)	C++14	43 / 100	3059 ms	62924 KiB

race

#include "race.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

#define pb push_back
#define ll long long
#define ii pair<int, int>
#define f1 first
#define s2 second

const int MAX = 2e5 + 7;
const int inf = 1e9 + 7;

int n, k;
int sz[MAX];
set<ii> adj[MAX];
static int ans;

int get_sz(int node, int par)
{
	sz[node] = 1;
	for (ii to : adj[node])
		if (to.f1 != par)
			sz[node] += get_sz(to.f1, node);
	return sz[node];
}

int centroid(int node, int par, int n)
{
	for (ii to : adj[node])
		if (to.f1 != par && sz[to.f1] > n/2)
			return centroid(to.f1, node, n);
	return node;
}

//{length, id}
//save two smalled length, but with different id
set<int> updated;
pair<ii, ii> ar[5 * MAX];

inline pair<ii, ii> combine (pair<ii, ii> _old, ii _new)
{
	vector<ii> v;
	v.pb(_old.f1);
	v.pb(_old.s2);
	v.pb(_new);
	sort(v.begin(), v.end());

	pair<ii, ii> res;
	res.f1 = v[0];
	if (v[0].s2 != v[1].s2) //different id
		res.s2 = v[1];
	else res.s2 = v[2];

	return res;
}

void dfs(int node, int par, int id, int dist, int h)
{
	if (dist > k)
		return;

	updated.insert(dist);
	ar[dist] = combine(ar[dist], {h, id});

	for (ii to : adj[node])
	{
		if (to.f1 != par)
			dfs(to.f1, node, id, dist + to.s2, h+1);
	}
}

void rc(int node)
{
	int n = get_sz(node, -1);
	int c = centroid(node, -1, n);
	vector<ii> edge(adj[c].begin(), adj[c].end());

	int id = 0;
	for (ii e : edge)
		dfs(e.f1, c, id++, e.s2, 1);

	if (updated.count(k))
		ans = min(ans, ar[k].f1.f1);
	for (int x : updated)
	{
		if (ar[x].f1.s2 != ar[k-x].f1.s2)
			ans = min(ans, ar[x].f1.f1 + ar[k-x].f1.f1);
		else ans = min(ans, ar[x].f1.f1 + ar[k-x].s2.f1);
	}

	for (int x : updated)
		ar[x] = {{inf, inf}, {inf, inf}};

	for (ii e : edge)
	{
		adj[c].erase(e);
		adj[e.f1].erase({c, e.s2});
		rc(e.f1);
	}
}

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]].insert({H[i][1], L[i]});
		adj[H[i][1]].insert({H[i][0], L[i]});
	}

	for (int i = 0; i < 5*MAX; ++i)
		ar[i] = {{inf, inf}, {inf, inf}};
	ans = n;

	rc(0);
	return ans == n ? -1 : ans;
}

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