Submission #24185

#	Time	Username	Problem	Language	Result	Execution time	Memory
24185		Bruteforceman	Race (IOI11_race)	C++11	100 / 100	603 ms	70180 KiB

race

#include "race.h"
#include "bits/stdc++.h"
using namespace std;

vector < pair <int, int> > g[200010];
int ans;
int len;

void dfs(int x, int par, map <long long, int> &f, long long &add, int &extra) {
	add = 0;
	extra = 0;
	f[0] = 0;

	for(auto i : g[x]) {
		if(i.first == par) continue;

		map <long long, int> t;
		long long plus;
		int rem;

		dfs(i.first, x, t, plus, rem);
		plus += i.second;
		rem += 1;

		if(t.size() > f.size()) {
			f.swap(t);
			swap(add, plus);
			swap(extra, rem);
		}
		for(auto i : t) {
			if(f.find(len - i.first - plus - add) != f.end()) {
				ans = min(ans, i.second + f[len - i.first - plus - add] + extra + rem);
			}
		}
		plus -= add;
		rem -= extra;
		for(auto i : t) {
			long long p = i.first + plus;
			if(f.find(p) == f.end()) {
				f[p] = i.second + rem;
			} else {
				f[p] = min(f[p], i.second + rem);
			}
		}
	}
}

int best_path(int N, int K, int H[][2], int L[])
{
	ans = INT_MAX;
	len = K;
	for(int i = 0; i <= N; i++) g[i].clear();
	for(int i = 0; i < N-1; i++) {
		int p = H[i][0];
		int q = H[i][1];
		int r = L[i];
		g[p].push_back(make_pair(q, r));
		g[q].push_back(make_pair(p, r));
	}
	map <long long, int> f;
	long long add;
	int extra;
	dfs(0, -1, f, add, extra);
	return ans == INT_MAX ? -1 : ans;
}

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