Submission #1126682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126682		Nonoze	Race (IOI11_race)	C++20	100 / 100	745 ms	38876 KiB

race

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

int n, k, ans=INT_MAX;
vector<vector<pair<int, int>>> adj;
vector<int> sz, centro;
map<int, int> mp;

void dfs(int u, int p=-1) {
	sz[u]=1;
	for (auto [v, w]: adj[u]) if (v!=p && !centro[v]) {
		dfs(v, u);
		sz[u]+=sz[v];
	}
}

int get_centroid(int u, int p, int obj) {
	for (auto [v, w]: adj[u]) if (v!=p && !centro[v] && sz[v]>=obj) return get_centroid(v, u, obj);
	return u;
}

void calc(int u, int p, int d, int sm, bool filling) {
	if (sm>k) return;
	if (filling) {
		if (mp.count(sm)) mp[sm]=min(mp[sm], d);
		else mp[sm]=d;
	}
	else if (mp.count(k-sm)) ans=min(ans, mp[k-sm]+d);
	for (auto [v, w]: adj[u]) if (v!=p && !centro[v]) calc(v, u, d+1, sm+w, filling);
}

int decompo(int u) {
	dfs(u);
	int c=get_centroid(u, -1, sz[u]/2); centro[c]=1;
	mp.clear(), mp[0]=0;
	for (auto [v, w]: adj[c]) if (!centro[v]) calc(v, c, 1, w, 0), calc(v, c, 1, w, 1);
	for (auto [v, w]: adj[c]) if (!centro[v]) decompo(v);
	return c;
}

int best_path(int N, int K, int H[][2], int L[]) {
	n=N, k=K;
	adj.resize(n);
	for (int i=0; i<n-1; i++) {
		adj[H[i][0]].push_back({H[i][1], L[i]});
		adj[H[i][1]].push_back({H[i][0], L[i]});
	}
	sz.resize(n), centro.resize(n);
	decompo(0);
	if (ans==INT_MAX) return -1;
	return ans;
}

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