oj.uz

Submission #308771

# Submission time Handle Problem Language Result Execution time Memory
308771 2020-10-01T22:18:27 Z wmrmr Mousetrap (CEOI17_mousetrap) C++17
0 / 100
 906 ms 77564 KB 
#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 mx = 0;
	for(int i=0;i<g[v].size();i++)
	{
		int prox = g[v][i];
		if(prox == p) continue;
		DFS1(prox,v);
		mx = max(mx,dp[prox]);
		dp[v] += 1+dp[prox];
	}
	dp[v] -= mx;
}

void DFS2(int v, int f, int ans)
{
	if(v == t)
	{
		printf("%d",ans); return;
	}
	int mx = 0;
	int cur = 0;
	for(int i=0;i<g[v].size();i++)
	{
		int prox = g[v][i];
		if(prox == f || prox == pai[v]) continue;
		mx = max(mx,dp[prox]);
		cur += dp[prox]+1;
	}
	cur -= mx;
	DFS2(pai[v],v,ans+cur);
}

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);
	}
	DFS1(t,0);
	DFS2(m,0,0);
}

Compilation message

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

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23936 KB Output is correct
2 Correct 16 ms 23808 KB Output is correct
3 Correct 16 ms 23808 KB Output is correct
4 Correct 16 ms 23808 KB Output is correct
5 Incorrect 17 ms 23808 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 76280 KB Output is correct
2 Correct 382 ms 71160 KB Output is correct
3 Incorrect 906 ms 77564 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23936 KB Output is correct
2 Correct 16 ms 23808 KB Output is correct
3 Correct 16 ms 23808 KB Output is correct
4 Correct 16 ms 23808 KB Output is correct
5 Incorrect 17 ms 23808 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23936 KB Output is correct
2 Correct 16 ms 23808 KB Output is correct
3 Correct 16 ms 23808 KB Output is correct
4 Correct 16 ms 23808 KB Output is correct
5 Incorrect 17 ms 23808 KB Output isn't correct
6 Halted 0 ms 0 KB -