Submission #446002

#	Time	Username	Problem	Language	Result	Execution time	Memory
446002		sinamhdv	Mousetrap (CEOI17_mousetrap)	C++11	100 / 100	1112 ms	209420 KiB

mousetrap

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fr first
#define sc second
#define endl '\n'

const int MAXN = 1000100;

int n, t, m;
vector<int> adj[MAXN];
int dp[MAXN];
int par[MAXN];
int prv[MAXN], nxt[MAXN];
vector<int> path;
vector<int> dpvec[MAXN];

void dfs1(int v)
{
	for (int u : adj[v]) if (u != par[v]) par[u] = v, dfs1(u);
}

void dfs2(int v)
{
	vector<int> vec;
	for (int u : adj[v]) if (u != par[v] && u != prv[v] && u != nxt[v]) dfs2(u), vec.pb(dp[u]);
	sort(all(vec), greater<int>());
	dp[v] = vec.size() + ((int)vec.size() >= 2 ? vec[1] : 0);
}

bool check(int x)
{
	int blk = 0;
	FOR(i, 0, (int)path.size())
	{
		int v = path[i];
		int cur = 0;
		for (int u : dpvec[v]) if (blk + u > x) cur++;
		blk += cur;
		if (blk > i + 1) return false;
	}
	return blk <= x;
}

int32_t main(void)
{
	fast_io;
	cin >> n >> t >> m;
	if (m == t) return cout << "0\n", 0;
	FOR(i, 0, n - 1)
	{
		int x, y;
		cin >> x >> y;
		adj[x].pb(y);
		adj[y].pb(x);
	}

	dfs1(m);
	int v = t;
	while (v != m)
	{
		nxt[par[v]] = v;
		prv[v] = par[v];
		path.pb(v);
		v = par[v];
	}
	path.pb(m);
	reverse(all(path));
	path.pop_back();

	for (int u : path) dfs2(u);
	dbgr(dp + 1, dp + n + 1);

	int sm = 0;
	for (int i = (int)path.size() - 1; i >= 0; i--)
	{
		int v = path[i];
		for (int u : adj[v]) if (v != prv[u] && v != nxt[u]) dpvec[v].pb(dp[u]);
		sm += dpvec[v].size();
		FOR(j, 0, (int)dpvec[v].size()) dpvec[v][j] += sm;
	}

	int l = -1, r = 3 * n + 10;
	while (r - l > 1)
	{
		int mid = (r + l) / 2;
		if (check(mid)) r = mid;
		else l = mid;
	}

	cout << r << endl;

	return 0;
}

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