Submission #703154

#	Time	Username	Problem	Language	Result	Execution time	Memory
703154		mosaev	Mousetrap (CEOI17_mousetrap)	C++17	100 / 100	921 ms	217252 KiB

mousetrap

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N ((ll)1e6+5)
#define M ((ll)1e9+7)
#define fi first
#define se second
ll n, t, m, st[N], ft[N], ct, w[N], dp[N], par[N], h[N], d[N], l, r, md;
vector<ll> v[N];
inline bool mpr(ll x) { return st[x] <= st[m] && ft[x] >= ft[m]; }
void dfs(ll s, ll p) {
	st[s] = ++ct; ll m1, m2; m1 = m2 = -1; h[s] = h[p] + 1;
	for (auto x : v[s]) if (x != p) {
		dfs(x, s); par[x] = s; if (!mpr(x)) {
			d[s]++; if (dp[x] >= m1) swap(m1, m2), m1 = dp[x]; else if (dp[x] >= m2) m2 = dp[x];
		}
	}
	dp[s] = d[s] + (d[s] > 1 ? m2 : 0); if (t == s) d[s] = 0;
	ft[s] = ++ct;
}
void wef(ll s, ll p) {
	w[s] += d[s]; for (auto x : v[s]) if (x != p) {
		w[x] = w[s], dp[x] += w[s]; wef(x, s);
	}
}
inline bool isv(ll x) {
	ll a = m, b, o = 0; while (a != t) {
		b = 0;
		for (auto y : v[a]) 
			if (!mpr(y) && dp[y] + o - b > x) 
				b++, o++;
		if (o > h[m] - h[a] + 1 || o > x) return false;
		a = par[a];
	}return true;
}
int32_t main() {
#define int ll
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> t >> m; ll a, b; for (int i = 1; i < n; i++) cin >> a >> b, v[a].push_back(b), v[b].push_back(a);
	dfs(t, 0); 
	wef(t, 0);
	l = -1; r = n; while (r - l > 1) {
		md = (r + l) / 2; if (isv(md)) r = md;
		else l = md;
	}
	cout << r;
}

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