Submission #1261060

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261060		kaiboy	Mousetrap (CEOI17_mousetrap)	C++20	100 / 100	382 ms	133436 KiB

mousetrap

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int   N = 1000000;
const int INF = 0x3f3f3f3f;

int *ej[N], eo[N];
int pp[N], ss[N], ii[N], dp[N];
bool used[N];

void append(int i, int j) {
	int o = eo[i]++;
	if (!o)
		ej[i] = (int *) malloc(sizeof *ej[i]);
	else if (!(o & o - 1))
		ej[i] = (int *) realloc(ej[i], (o << 1) * sizeof *ej[i]);
	ej[i][o] = j;
}

void detach(int i, int j) {
	for (int o = 0; o < eo[i]; o++)
		if (ej[i][o] == j) {
			swap(ej[i][o], ej[i][--eo[i]]);
			return;
		}
}

void dfs_pp(int p, int i) {
	pp[i] = p;
	for (int o = 0; o < eo[i]; o++) {
		int j = ej[i][o];
		if (j != p)
			dfs_pp(i, j);
	}
}

void dfs_ss(int p, int i, int s) {
	ss[i] = s += eo[i] - 2;
	for (int o = 0; o < eo[i]; o++) {
		int j = ej[i][o];
		if (j != p)
			dfs_ss(i, j, s);
	}
}

void dfs_dp(int i) {
	int x = 0, y = 0;
	for (int o = 0; o < eo[i]; o++) {
		int j = ej[i][o];
		dfs_dp(j);
		int z = dp[j];
		if (x < z)
			y = x, x = z;
		else if (y < z)
			y = z;
	}
	dp[i] = y + eo[i];
}

bool check(int k, int x) {
	for (int d = 0, h = k - 1; h >= 0; h--) {
		int i = ii[h], s = h ? ss[ii[h - 1]] : 0;
		int o = 0, o_ = eo[i];
		while (o < o_ && dp[ej[i][o]] + o_ + s <= x)
			o++;
		if ((++d -= o_ - o) < 0 || (x -= o_ - o) < 0)
			return false;
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, s, t; cin >> n >> t >> s, s--, t--;
	for (int h = 0; h < n - 1; h++) {
		int i, j; cin >> i >> j, i--, j--;
		append(i, j), append(j, i);
	}
	dfs_pp(-1, s);
	if (s != t)
		dfs_ss(t, pp[t], 0);
	for (int i = 0; i < n; i++)
		detach(i, pp[i]);
	int k = 0;
	for (int i = t; i != s; i = pp[i])
		detach(ii[k++] = pp[i], i);
	for (int h = 0; h < k; h++) {
		int i = ii[h];
		for (int o = 0; o < eo[i]; o++)
			dfs_dp(ej[i][o]);
		sort(ej[i], ej[i] + eo[i], [] (int j0, int j1) { return dp[j0] < dp[j1]; });
	}
	int lower = -1, upper = INF;
	while (upper - lower > 1) {
		int x = lower + upper >> 1;
		if (check(k, x))
			upper = x;
		else
			lower = x;
	}
	cout << upper << '\n';
	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 20 / 20
• Subtask 4: 35 / 35