Submission #263339

#	Time	Username	Problem	Language	Result	Execution time	Memory
263339		Berted	Race (IOI11_race)	C++14	100 / 100	478 ms	99592 KiB

race

#include "race.h"
#include <vector>
#include <iostream>
#include <set>
#define ll long long
#define vi vector<int>
#define pii pair<ll, ll>
#define fst first
#define snd second
#define vpi vector<pii>
#define pub push_back
#define spi set<pii>

using namespace std;

const int INF = 1e9;

vpi adj[200001];
int ans = INF, k;

struct DS
{
	ll a = 0, b = 0; set<pii> s;
	void insert(ll x, ll y) {s.insert({x - a, y - b});}
	void offset(ll x, ll y) {a += x; b += y;}
	int size() {return s.size();}
	int retMin(ll t)
	{
		auto it = s.upper_bound({t - a, -1000000000});
		if (it != s.end() && it -> fst + a == t) return it -> snd + b;
		else return INF;
	}
};

DS* DFS(int u, int p, int pv)
{
	DS* ret = nullptr;
	for (auto v : adj[u])
	{
		if (v.fst != p)
		{
			DS* ret2 = DFS(v.fst, u, v.snd);
			if (ret == nullptr) {ret = ret2;}
			else if (ret -> size() < ret2 -> size())
			{
				for (const auto &v : ret -> s)
				{
					ll vv = v.fst + ret -> a;
					ans = min(ans, (int)ret -> b + (int)v.snd + ret2 -> retMin(k - vv));
				}
				for (const auto &v : ret -> s)
				{
					ret2 -> insert(v.fst + ret -> a, v.snd + ret -> b);
				}
				swap(ret, ret2);
			}
			else
			{
				for (const auto &v : ret2 -> s)
				{
					ll vv = v.fst + ret2 -> a;
					ans = min(ans, (int)ret2 -> b + (int)v.snd + ret -> retMin(k - vv));
				}
				for (const auto &v : ret2 -> s)
				{
					ret -> insert(v.fst + ret2 -> a, v.snd + ret2 -> b);
				}
			}
		}
	}
	if (ret == nullptr) {ret = new DS;}
	ret -> insert(0, 0);
	ans = min(ans, ret -> retMin(k));

	/*cout << "Node " << u << " " << p << " " << ret -> a << " " << ret -> b << ":\n";
	for (auto x : ret -> s)
	{
		cout << x.fst + ret -> a << ", " << x.snd + ret -> b << "\n";
	}*/

	ret -> offset(pv, 1);
	return ret;
}

int best_path(int N, int K, int H[][2], int L[])
{
	k = K;
	for (int i = 0; i < N - 1; i++)
	{
		adj[H[i][0]].emplace_back(H[i][1], L[i]);
		adj[H[i][1]].emplace_back(H[i][0], L[i]);
	}
	DFS(0, -1, 0);
	if (ans == INF) return -1;
	else return ans;
}

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