Submission #851419

#	Time	Username	Problem	Language	Result	Execution time	Memory
851419		mat_jur	Race (IOI11_race)	C++17	100 / 100	493 ms	86880 KiB

race

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define debug(X) ;
#endif
#define ll long long
#define all(v) (v).begin(), (v).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define ROF(i,r,l) for(int i=(r);i>=(l);--i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

int best_path(int n, int k, int h[][2], int l[]) {
	vector<vector<pair<int, int>>> G(n);
	REP(i, n-1) {
		G[h[i][0]].eb(mp(h[i][1], l[i]));
		G[h[i][1]].eb(mp(h[i][0], l[i]));
	}
	const int inf = 1e9;
	int res = inf;
	vector<pair<pair<int, int>, map<int, int>>> M(n);
	auto merge = [&](pair<pair<int, int>, map<int, int>> &a, pair<pair<int, int>, map<int, int>> &b) {
		if (ssize(a.se) < ssize(b.se)) swap(a, b);
		for (auto x : b.se) {
			int key = x.fi+b.fi.fi;
			if(a.se.find((k-key)-a.fi.fi) != a.se.end()) res = min(res, a.se[(k-key)-a.fi.fi]+a.fi.se+x.se+b.fi.se);
		}
		for (auto x : b.se) {
			int key = x.fi+b.fi.fi;
			if (a.se.find(key-a.fi.fi) == a.se.end()) a.se[key-a.fi.fi] = inf;
			a.se[key-a.fi.fi] = min(a.se[key-a.fi.fi], x.se+b.fi.se-a.fi.se);
		}
		return;
	};
	function<void(int, int)> dfs = [&](int v, int p) {
		M[v].fi.fi = M[v].fi.se = 0;
		M[v].se[0] = 0;
		for (auto e : G[v]) {
			int u = e.fi, w = e.se;
			if (u == p) continue;
			dfs(u, v);
			M[u].fi.fi += w;
			M[u].fi.se++;
			merge(M[v], M[u]);
		}
	};
	dfs(0, -1);
	if (res == inf) return -1;
	return res;
}

#ifdef LOCAL
int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, k;
	cin >> n >> k;
	int h[n-1][2];
	int l[n-1];
	REP(i, n-1) {
		cin >> h[i][0] >> h[i][1];
	}	
	REP(i, n-1) {
		cin >> l[i];
	}
	cout << best_path(n, k, h, l) << '\n';
	return 0;
}
#endif

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