Submission #62435

#	Time	Username	Problem	Language	Result	Execution time	Memory
62435		Sherazin	Race (IOI11_race)	C++14	0 / 100	6 ms	5116 KiB

race

#include "race.h"
#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 2e5 + 5;
const int M = 1e6 + 5;

int n, k, book;
int ans = -1;
int sub[N], dp[M], tim[M];
vector<pii> g[N];
bitset<N> chk;
pii cent;

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

void centroid(int u, int p, int all) {
	pii mxsub(all - sub[u], u);
	for(pii v : g[u]) if(v.x != p && !chk[v.x]) {
		centroid(v.x, u, all);
		mxsub = max(mxsub, pii(sub[v.x], u));
	}
	if(mxsub < cent) cent = mxsub;
}

void dfs(int u, int p, int len, int cnt) {
	if(len > k) return;
	if(tim[k - len] == book) if(ans == -1 || cnt + dp[k - len] < ans) ans = cnt + dp[k - len];
	if(len == k && (ans == -1 || cnt < ans)) ans = cnt;
	for(pii v : g[u]) if(v.x != p && !chk[v.x]) dfs(v.x, u, len + v.y, cnt + 1);
}

void prep(int u, int p, int len, int cnt) {
	if(len > k) return;
	if(tim[len] < book || cnt < dp[len]) tim[len] = book, dp[len] = cnt;
	for(pii v : g[u]) if(v.x != p && !chk[v.x]) dfs(v.x, u, len + v.y, cnt + 1);
}

void proc(int u) {
	book++;
	if(calcsz(u, u) <= 1) return;
	cent = pii(sub[u], u);
	centroid(u, u, sub[u]);
	u = cent.y;
	for(pii v : g[u]) if(!chk[v.x]) {
		dfs(v.x, u, v.y, 1);
		prep(v.x, u, v.y, 1);
	}
	chk[u] = 1;
	for(pii v : g[u]) if(!chk[v.x]) proc(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]);
	}

	proc(0);
	return ans;
}

/*int main() {
	int n, k, h[100][2], l[100];
	scanf("%d%d", &n, &k);
	for(int i = 0; i < n - 1; i++) {
		scanf("%d %d %d", &h[i][0], &h[i][1], &l[i]);
	}
	printf("%d", best_path(n, k, h, l));

	return 0;
}*/

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