oj.uz

Submission #878720

# Submission time Handle Problem Language Result Execution time Memory
878720 2023-11-25T06:19:35 Z Faisal_Saqib Mousetrap (CEOI17_mousetrap) C++17
45 / 100
 1571 ms 149144 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(auto i:path)
	// 	cout<<i<<' ';
	// cout<<endl;
	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()>0 and wela>0)
		{
			ansp++;
			apo.pop_back();
			wela--;
		}
		if(apo.size()==0)
			ansp+=0;
		else
		{
			ansp+=apo.back()+apo.size();
		}
	}
	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:85: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]
   85 |  for(int i=0;i+1<path.size();i++)
      |              ~~~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 48732 KB Output is correct
2 Correct 12 ms 48888 KB Output is correct
3 Correct 11 ms 48732 KB Output is correct
4 Correct 10 ms 48732 KB Output is correct
5 Correct 10 ms 48732 KB Output is correct
6 Correct 12 ms 48732 KB Output is correct
7 Correct 10 ms 48732 KB Output is correct
8 Correct 10 ms 48892 KB Output is correct
9 Correct 10 ms 48852 KB Output is correct
10 Correct 10 ms 48732 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 148944 KB Output is correct
2 Correct 549 ms 139560 KB Output is correct
3 Correct 1571 ms 149136 KB Output is correct
4 Correct 697 ms 100116 KB Output is correct
5 Correct 1467 ms 149144 KB Output is correct
6 Correct 1483 ms 149140 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 48732 KB Output is correct
2 Correct 12 ms 48888 KB Output is correct
3 Correct 11 ms 48732 KB Output is correct
4 Correct 10 ms 48732 KB Output is correct
5 Correct 10 ms 48732 KB Output is correct
6 Correct 12 ms 48732 KB Output is correct
7 Correct 10 ms 48732 KB Output is correct
8 Correct 10 ms 48892 KB Output is correct
9 Correct 10 ms 48852 KB Output is correct
10 Correct 10 ms 48732 KB Output is correct
11 Correct 610 ms 148944 KB Output is correct
12 Correct 549 ms 139560 KB Output is correct
13 Correct 1571 ms 149136 KB Output is correct
14 Correct 697 ms 100116 KB Output is correct
15 Correct 1467 ms 149144 KB Output is correct
16 Correct 1483 ms 149140 KB Output is correct
17 Incorrect 10 ms 48732 KB Output isn't correct
18 Halted 0 ms 0 KB -