Submission #513859

#	Time	Username	Problem	Language	Result	Execution time	Memory
513859		Eyed	Race (IOI11_race)	C++17	100 / 100	498 ms	109136 KiB

race

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll MOD = 1e9 + 7;

//IOI 2011 Race
// Problem: https://oj.uz/problem/view/IOI11_race

struct edge {
	ll b;
	ll w;
	edge(ll a = 0, ll y = 0) : b(a), w(y) {};
};

vector<edge> tree[200005];
map<ll, ll> dists[200005];
ll minK[200005];
ll addTo[200005]; //d + addTo[x] = trueDist;
ll addN[200005]; //ns + addN[x] = trueNs;

void dfs(ll x, ll p, ll k) {
	dists[x][0] = 0;
	minK[x] = 1e9;
	addTo[x] = 0;
	addN[x] = 0;
	if (k == 0) minK[x] = 0;	
	for (edge e : tree[x]) {
		ll v = e.b;
		ll c = e.w;
		if (v == p) continue;
		dfs(v, x, k);
		minK[x] = min(minK[x], minK[v]);
		if (dists[v].size() <= dists[x].size()) {
			for (auto itr = dists[v].begin(); itr != dists[v].end(); ++itr) {
				ll d = itr->first + addTo[v];
				ll ns = itr->second + addN[v];
				if (dists[x].find(k - d - c - addTo[x]) != dists[x].end()) minK[x] = min(minK[x], ns + 1 + dists[x][k - d -c - addTo[x]] + addN[x]);
			}
			for (auto itr = dists[v].begin(); itr != dists[v].end(); ++itr) {
				ll d = itr->first + addTo[v];
				ll ns = itr->second + addN[v];
				if (dists[x].find(d + c - addTo[x]) != dists[x].end()) dists[x][d + c - addTo[x]] = min(dists[x][d + c - addTo[x]], ns + 1 - addN[x]);
				else dists[x][d + c - addTo[x]] = ns + 1 - addN[x];
			}
		}
		else {
			dists[x].swap(dists[v]);
			for (auto itr = dists[v].begin(); itr != dists[v].end(); ++itr) {
				ll d = itr->first + addTo[x];
				ll ns = itr->second + addN[x];
				if (dists[x].find(k - d - c - addTo[v]) != dists[x].end()) minK[x] = min(minK[x], ns +1 + dists[x][k - d - c - addTo[v]] + addN[v]);
			}
			for (auto itr = dists[v].begin(); itr != dists[v].end(); ++itr) {
				ll d = itr->first + addTo[x] - addTo[v] - c;
				ll ns = itr->second + addN[x] - addN[v] - 1;
				if (dists[x].find(d) != dists[x].end()) dists[x][d] = min(dists[x][d], ns);
				else dists[x][d] = ns;
			}
			addTo[x] = addTo[v] + c;
			addN[x] = addN[v] + 1;
		}
	}
}

int best_path(int N, int K, int H[][2], int L[]) {
	for (ll i = 0; i < N - 1; ++i) {
		tree[H[i][0]].push_back(edge(H[i][1], L[i]));
		tree[H[i][1]].push_back(edge(H[i][0], L[i]));
	}
	dfs(0, 0, K);
	if (minK[0] != 1e9) return minK[0];
	return -1;
}

//ll main() {
//	ios::sync_with_stdio(0);
//	cin.tie(0);
//
//	ll H[10][2] = { {0,1}, {0,2}, {2,3}, {3,4}, {4,5}, {0,6}, {6,7}, {6,8}, {8,9}, {8,10} };
//	ll L[10] = { 3,4,5,4,6,3,2,5,6,7};
//	cout << best_path(11, 12, H, L) << endl;
//
//
//	return 0;
//}

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