Submission #445967

#	Time	Username	Problem	Language	Result	Execution time	Memory
445967		minoum	Mousetrap (CEOI17_mousetrap)	C++17	25 / 100	1340 ms	127188 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], 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){
	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];
	}
	if(cnt[v]==0){
		dp[v] = 0; return;
	}
	int mx1 = 0, mx2 = 0;
	for(auto i: adj[v]){
		int u = i.first, id = i.second;
		if(u==parv || mark[id]) continue;
		if(dp[u]>mx1) mx2 = mx1, mx1 = dp[u];
		else if(dp[u]>mx2) mx2 = dp[u];
	}
	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 << ans[st] << endl;
	return 0; 
}

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