oj.uz

Submission #878714

# Submission time Handle Problem Language Result Execution time Memory
878714 2023-11-25T06:13:22 Z Faisal_Saqib Mousetrap (CEOI17_mousetrap) C++17
0 / 100
 575 ms 149172 KB 
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
#define int long long
const int N=1e6+2;
set<int> ma[N];
int dp[N]; // dp[x] = def = what is the minimum number of step(Of Kalu ustad) return back to x,such that the subtree of x  are  the only cities you can go to
int n,t,m;
int from,to;
vector<int> path,prefix;
void find_path(int x,int p=-1)
{
	prefix.push_back(x);
	if(to==x)
	{
		while(prefix.back()!=from)
		{
			path.push_back(prefix.back());
			prefix.pop_back();
		}
		int i=((int)path.size())-1;
		path.push_back(from);
		while(i>=0 and prefix.back()!=to)
		{
			prefix.push_back(path[i]);
			i--;
		}
	}
	for(auto y:ma[x])
		if(y!=p)
			find_path(y,x);
	prefix.pop_back();
}
void dfs(int x,int p=-1)
{
	// cout<<"Component main ha "<<x<<endl;
	int total=0;
	for(auto y:ma[x])
	{
		if(y!=p)
		{
			dfs(y,x);
			total++;
		}
	}
	int mx=0;
	int mx2=0;
	for(auto y:ma[x])
	{
		if(y!=p)
		{
			if(dp[y]>mx)
			{
				mx2=mx;
				mx=dp[y];
			}
			else if(dp[y]>mx2)
			{
				mx2=dp[y];
			}
		}
	}
	dp[x]=mx2+total;
}
signed main()
{
	cin>>n>>t>>m;
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		ma[x].insert(y);
		ma[y].insert(x);
	}
	from=t;
	to=m;
	find_path(from);
	long long ansp=0;
	int wela=0;
	for(int i=0;i+1<path.size();i++)
	{
		// Remove edge 
		wela++;
		int x=path[i+1];
		int y=path[i];
		ma[x].erase(y);
		ma[y].erase(x);
		dfs(y);
		vector<int> apo;
		for(auto y:ma[y])
			apo.push_back(dp[y]);
		sort(begin(apo),end(apo));
		while(apo.size() and wela--)
		{
			ansp++;
			apo.pop_back();
		}
		if(apo.size()==0)
		{
			apo.push_back(0);
		}
		ansp+=apo.back();
		// cout<<wela<<' '<<apo.size()<<endl;
		// ansp+=dp[y];
		// cout<<"For "<<y<<' ';
		// cout<<dp[y]<<endl;
	}
	cout<<ansp<<endl;
	// cout<<endl;
	// cout<<dp[m]<<endl;
	// for(int i=1;i<=n;i++)
	// {
	// 	cout<<"for" <<i<<' '<<dp[i]<<endl;
	// }
	return 0;
}

Compilation message

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:82:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  for(int i=0;i+1<path.size();i++)
      |              ~~~^~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 48732 KB Output is correct
2 Correct 9 ms 48732 KB Output is correct
3 Correct 10 ms 48884 KB Output is correct
4 Correct 10 ms 48732 KB Output is correct
5 Correct 10 ms 48732 KB Output is correct
6 Correct 10 ms 48892 KB Output is correct
7 Incorrect 10 ms 48732 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 575 ms 149172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 48732 KB Output is correct
2 Correct 9 ms 48732 KB Output is correct
3 Correct 10 ms 48884 KB Output is correct
4 Correct 10 ms 48732 KB Output is correct
5 Correct 10 ms 48732 KB Output is correct
6 Correct 10 ms 48892 KB Output is correct
7 Incorrect 10 ms 48732 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 48732 KB Output is correct
2 Correct 9 ms 48732 KB Output is correct
3 Correct 10 ms 48884 KB Output is correct
4 Correct 10 ms 48732 KB Output is correct
5 Correct 10 ms 48732 KB Output is correct
6 Correct 10 ms 48892 KB Output is correct
7 Incorrect 10 ms 48732 KB Output isn't correct
8 Halted 0 ms 0 KB -