Submission #878722

#	Time	Username	Problem	Language	Result	Execution time	Memory
878722		Jawad_Akbar_JJ	Mousetrap (CEOI17_mousetrap)	C++14	0 / 100	107 ms	22812 KiB

mousetrap

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 2e5  + 10;
vector<int> nei[N];
int par[N];
int Mx1[N];
int Mx2[N];

void Dfs(int u,int p = -1){
	par[u] = p;
	
	for (int i : nei[u]){
		if (i==p)
			continue;
		Dfs(i,u);
		int mx = Mx2[i] + 1;
		if (mx>Mx1[u]){
			Mx2[u] = Mx1[u];
			Mx1[u] = mx;
		}
		else
			Mx2[u] = max(Mx2[u],mx);
	}
}

signed main(){
	int n,t,m;
	cin>>n>>t>>m;
	
	for (int i=2;i<=n;i++){
		int u,v;
		cin>>u>>v;
		nei[u].push_back(v);
		nei[v].push_back(u);
	}
	
	Dfs(t);
	
	// for (int i=1;i<=n;i++)
		// cout<<Mx1[i]<<" "<<Mx2[i]<<endl;
	int mx = 0;
	int Mx = 1;
	for (int i : nei[m]){
		if (i==t)
			continue;
		if (Mx1[i] + 1>Mx){
			mx = Mx;
			Mx = Mx1[i] + 1;
		}
		else
			mx = max(mx,Mx1[i] + 1);
	}
	
	int flag = true;
	int block = 0;
	for (int i : nei[m]){
		if (i==t)
			continue;
		block++;
	}
	if (Mx==0){
		cout<<0<<endl;
	}
	else if (mx == 0){
		cout<<1<<endl;
	}
	else
		cout<<block + mx - 1<<endl;
}

Compilation message (stderr)

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:57:6: warning: unused variable 'flag' [-Wunused-variable]
   57 |  int flag = true;
      |      ^~~~

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