Submission #308779

#	Time	Username	Problem	Language	Result	Execution time	Memory
308779		wmrmr	Mousetrap (CEOI17_mousetrap)	C++17	0 / 100	415 ms	62984 KiB

mousetrap

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e6+10;
int dp[MAX], pai[MAX];
int n,t,m;
vector<int> g[MAX];

void DFS1(int v, int p)
{
	pai[v] = p;
	int grau = g[v].size();
	pair<int,int> mx; mx = {-1,-1};
	if(grau==2)
	{
		dp[v] = 1; return;
	}
	for(int i=0;i<grau;i++)
	{
		int prox = g[v][i];
		if(prox == p) continue;
		DFS1(prox,v);
		if(dp[prox] >= mx.first)
			mx.second = mx.first, mx.first = dp[prox];
		else if(dp[prox] > mx.second)
			mx.second = dp[prox];
	}
	dp[v] = grau + mx.second - 1;
}

void DFS2(int v, int f, int ans)
{
	if(v == t)
	{
		printf("%d",ans); return;
	}
	if(f == 0)
	{
		DFS2(pai[v],v,dp[v]); return;
	}
	int grau = g[v].size();
	if(grau == 2)
	{
		DFS2(pai[v],v,ans); return;
	}
	if(grau == 3)
	{
		DFS2(pai[v],v,ans+1); return;
	}
	pair<int,int> mx; mx = {-1,-1};
	for(int i=0;i<g[v].size();i++)
	{
		int prox = g[v][i];
		if(prox == f || prox == pai[v]) continue;
		if(dp[prox] >= mx.first)
			mx.second = mx.first, mx.first = dp[prox];
		else if(dp[prox] > mx.second)
			mx.second = dp[prox];
	}
	DFS2(pai[v],v,ans+grau+mx.second-2);
}

int main()
{
	scanf("%d %d %d",&n,&t,&m);
	for(int i=1;i<n;i++)
	{
		int a,b; scanf("%d %d",&a,&b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(int i=0;i<g[t].size();i++)
	{
		int prox = g[t][i];
		DFS1(prox,t);
	}
	DFS2(m,0,0);
}

Compilation message (stderr)

mousetrap.cpp: In function 'void DFS2(int, int, int)':
mousetrap.cpp:50:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i=0;i<g[v].size();i++)
      |              ~^~~~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:71:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for(int i=0;i<g[t].size();i++)
      |              ~^~~~~~~~~~~~
mousetrap.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |  scanf("%d %d %d",&n,&t,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:67:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |   int a,b; scanf("%d %d",&a,&b);
      |            ~~~~~^~~~~~~~~~~~~~~

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