Submission #1253091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253091		kaiboy	Mousetrap (CEOI17_mousetrap)	C++20	0 / 100	325 ms	48512 KiB

mousetrap

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1000000;

int *ej[N], eo[N], dp[N], ii[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;
		}
}

bool dfs(int p, int i, int t) {
	detach(i, p);
	bool yes = i == t;
	for (int o = 0; o < eo[i]; o++) {
		int j = ej[i][o];
		if (dfs(i, j, t))
			yes = true, swap(ej[i][o], ej[i][0]);
	}
	return yes;
}

void dfs0(int i) {
	for (int o = 0; o < eo[i]; o++)
		dfs0(ej[i][o]);
	sort(ej[i], ej[i] + eo[i], [] (int j0, int j1) { return dp[j0] > dp[j1]; });
	dp[i] = eo[i];
	for (int o = 1; o < eo[i]; o += 2)
		dp[i] += dp[ej[i][o]];
}

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(-1, s, t);
	int k = 0;
	for (int i = s, j; i != t; i = j) {
		j = ej[ii[k++] = i][0];
		for (int o = 1; o < eo[i]; o++)
			dfs0(ej[i][o - 1] = ej[i][o]);
		sort(ej[i], ej[i] + --eo[i], [] (int j0, int j1) { return dp[j0] > dp[j1]; });
	}
	int ans = eo[ii[0]] + eo[ii[1]];
	for (int o = 1; o < eo[ii[0]]; o += 2)
		ans += dp[ej[ii[0]][o]];
	for (int o = (eo[ii[0]] % 2 == 0) + 1; o < eo[ii[1]]; o += 2)
		ans += dp[ej[ii[1]][o]];
	cout << ans << '\n';
	return 0;
}

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