Submission #445965

#	Time	Username	Problem	Language	Result	Execution time	Memory
445965		minoum	Mousetrap (CEOI17_mousetrap)	C++17	0 / 100	461 ms	132080 KiB

mousetrap

#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

const int MAXN = 1e6+10;

int n, st, e, p[MAXN], pid[MAXN], dp[MAXN], ans[MAXN], sz[MAXN], cnt[MAXN], bns[MAXN], ans2[MAXN], bns2[MAXN];
bool mark[MAXN], stuck[MAXN];
vector <pair<int,int>> adj[MAXN];
vector <pair<int,int>> ch[MAXN];

inline void dfs(int v, int parv){
	sz[v] = 1;
	for(auto i: adj[v]){
		if(i.first==parv) continue;
		p[i.first] = v;
		pid[i.first] = i.second;
		dfs(i.first, v);
		sz[v] += sz[i.first];
	}
	return;
}

inline void dfs1(int v, int parv){
	bns[v] = 1; bns2[v] = 1;
	for(auto i: adj[v]){
		int u = i.first, id = i.second;
		if(u==parv) continue;
		if(!mark[id]) cnt[v]++;
		dfs1(u,v);
		ch[v].push_back({dp[u],u});
		if(mark[id]){
			ans[v] += ans[u], bns[v]+=bns[u];
			stuck[v] |= stuck[u]; ans2[v] += ans2[u];
		} 
	}
	sort(ch[v].begin(), ch[v].end());
	reverse(ch[v].begin(), ch[v].end());
	if(cnt[v]==0){
		dp[v] = 0; 
		return;
	}
	int mx2 = (bns[v]>=(int)ch[v].size()?0:ch[v][bns[v]].first);
	if(stuck[v]){
		ans2[v] += cnt[v];
	}
	if(bns[v]<(int)ch[v].size()){
		stuck[v] = true; ans2[v] = min(ans2[v],ans2[ch[v][bns[v]].second]+cnt[v]-1);
		bns[v] = n;
	} 
	else bns[v] = max(0, bns[v]-(int)ch[v].size());
	dp[v] = 1+mx2+(cnt[v]>1?cnt[v]-1:0); ans[v]+=dp[v];
	return;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> st >> e; st--; e--;
	for(int i = 0; i < n-1; i++){
		int u,v;
		cin >> u >> v; u--; v--;
		adj[u].push_back({v,i});
		adj[v].push_back({u,i});
	}
	dfs(st,-1);
	int u = e;
	while(u!=st){
		mark[pid[u]] = true;
		u = p[u];
	}
	dfs1(st,-1);
	cout << min(ans[st],ans2[st]) << endl;
	return 0; 
}

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