Submission #40998

#	Time	Username	Problem	Language	Result	Execution time	Memory
40998		win11905	Race (IOI11_race)	C++11	100 / 100	938 ms	34684 KiB

race

#include <bits/stdc++.h>
#define P pair<int, int>
#define x first
#define y second
using namespace std;

const int MAXN = 2e5 + 50, MAXK = 1e6 + 50;

int n, k, snode, curmx, ans, cnt, size[MAXN], dp[MAXK], mpath[MAXK];
bool chk[MAXN];
vector<P> g[MAXN];

int dfs(int u, int p) {
	size[u] = 1;
	for(auto v : g[u]) if(!chk[v.x] && v.x != p) {
		dfs(v.x, u);
		size[u] += size[v.x];
	}
	return size[u];
}

void findsen(int u, int p, int d) {
	int mx = (d - size[u]);
	for(auto v : g[u]) if(!chk[v.x] && v.x != p) {
		findsen(v.x, u, d);
		mx = max(mx, size[v.x]);
	}
	if(mx < curmx) snode = u, curmx = mx;
}

void dfs1(int u, int p, int cost, int len, bool fill) {
	if(cost > k) return;
	if(!fill) {
		if(dp[k-cost] == cnt && (len + mpath[k-cost] < ans || ans == -1)) ans = len + mpath[k-cost];
		if(cost == k && (len < ans || ans == -1)) ans = len;
	} else if(dp[cost] < cnt || len < mpath[cost]) dp[cost] = cnt, mpath[cost] = len;
	for(auto v : g[u]) if(!chk[v.x] && v.x != p) dfs1(v.x, u, cost + v.y, len + 1, fill);
}

void process(int u) {
	++cnt;
	if(dfs(u, -1) <= 1) return;
	curmx = size[u] + 1;
	findsen(u, -1, size[u]);
	u = snode;
	for(auto v : g[u]) if(!chk[v.x]) dfs1(v.x, snode, v.y, 1, 0), dfs1(v.x, snode, v.y, 1, 1);
	chk[u] = true;
	for(auto v : g[u]) if(!chk[v.x]) process(v.x);
}

int best_path(int _n, int _k, int h[][2], int l[]) {
	n = _n, k = _k;
	for(int i = 0; i < n-1; ++i) {
		g[h[i][0]].emplace_back(h[i][1], l[i]);
		g[h[i][1]].emplace_back(h[i][0], l[i]);
	}
	cnt = 0;
	ans = -1;
	process(0);
	return ans;
}

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