Submission #378697

#	Time	Username	Problem	Language	Result	Execution time	Memory
378697		penguinhacker	Race (IOI11_race)	C++14	100 / 100	497 ms	78328 KiB

race

// source: https://oj.uz/problem/view/IOI11_race
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN = 200000;
const int INF = 1e9;
int n, k, ans;
vector<pair<int, int>> adj[mxN];
map<int, int> paths[mxN];
pair<int, int> offset[mxN];

void upd(map<int, int>& m, int x, int y) {
	auto it = m.find(x);
	if (it == m.end())
		m[x] = y;
	else if (y < it->second)
		it->second = y;
}

int qry(int u, int x) {
	auto it = paths[u].find(x);
	return it == paths[u].end() ? INF : it->second + offset[u].second;
}

void dfs(int u = 0, int p = -1) {
	upd(paths[u], 0, 0);
	for (pair<int, int> v : adj[u]) {
		if (v.first == p)
			continue;
		dfs(v.first, u);
		offset[v.first].first += v.second;
		++offset[v.first].second;
		if (paths[v.first].size() > paths[u].size()) {
			swap(paths[u], paths[v.first]);
			swap(offset[u], offset[v.first]);
		}
		for (auto& x : paths[v.first]) {
			pair<int, int> real = {x.first + offset[v.first].first, x.second + offset[v.first].second};
			if (real.first > k)
				continue;
			ans = min(ans, real.second + qry(u, k - real.first - offset[u].first));
		}
		for (auto& x : paths[v.first]) {
			pair<int, int> real = {x.first + offset[v.first].first, x.second + offset[v.first].second};
			if (real.first > k)
				continue;
			upd(paths[u], real.first - offset[u].first, real.second - offset[u].second);
		}
		map<int, int>().swap(paths[v.first]);
	}
}

int best_path(int _n, int _k, int h[][2], int l[]) {
	n = _n, k = _k, ans = INF;
	for (int i = 0; i < n - 1; ++i) {
		int u = h[i][0], v = h[i][1], w = l[i];
		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);
	}
	dfs();
	return ans == INF ? -1 : ans;
}

/*
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, k; cin >> n >> k;
	int h[n - 1][2];
	int l[n - 1];
	for (int i = 0; i < n - 1; ++i) {
		cin >> h[i][0] >> h[i][1];
	}
	for (int i = 0; i < n - 1; ++i) {
		cin >> l[i];
	}
	cout << best_path(n, k, h, l);
	return 0;
}
*/

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