oj.uz

Submission #704593

# Submission time Handle Problem Language Result Execution time Memory
704593 2023-03-02T11:31:04 Z amirhoseinfar1385 Mousetrap (CEOI17_mousetrap) C++17
45 / 100
 883 ms 116088 KB 
#include<bits/stdc++.h>
using namespace std;

const int maxn=1000000+5;
vector<int>adj[maxn],alldp[maxn];
int par[maxn],vis[maxn],n,t,m,dp[maxn],ted[maxn],mainres;
int val[maxn],high[maxn];

struct compare
{
    bool operator()(const pair<int,int> & a, const pair<int,int> & b)
    {
        if(a.first==b.first){
        	return high[a.second]<high[b.second];
        }
        return a.first<b.first;
    }
};

priority_queue<pair<int,int>,vector<pair<int,int>>,compare>pq;


void dfs(int u,int para=0){
	par[u]=para;
	high[u]=high[para]+1;
	for(int x:adj[u])
	{
		if(x!=para){
			dfs(x,u);
			vis[u]|=vis[x];
			if(vis[x]==0){
				ted[u]++;
				alldp[u].push_back(dp[x]);
			}	
		}
	}
	if((int)alldp[u].size()>0){
		if((int)alldp[u].size()==1){
			dp[u]=2;
		}
		else{
			sort(alldp[u].begin(),alldp[u].end());
			int maxa1=alldp[u].back(),maxa2=alldp[u][(int)alldp[u].size()-2];
			dp[u]=maxa2+ted[u]-1;
			dp[u]++;
		}
	}	
	else{
		dp[u]=1;
	}
}

void solve(int had){
	int allted=0,now=had;
	while(now!=t){
		//cout<<"1 "<<now<<endl;
		allted+=ted[now];
		now=par[now];
	}
	int fted=allted;
	now=had;
	int unnow=1;
	while(now!=t){
		int ffted=allted;
		for(int i=(int)alldp[now].size()-1;i>=0;i--){
			int x=alldp[now][i]+allted-1+(int)pq.size();
			if((int)pq.size()<unnow){
				pq.push(make_pair(x,now));
				val[now]++;
				allted--;
			}
			else{
				pair<int,int> y=pq.top();
				if(y.first<=x){
					pq.pop();
					pq.push(make_pair(x,now));
					val[y.second]--;
					val[now]++;
					allted--;
					if(y.second==now){
						allted++;
					}
				}
			}
		}
		allted=ffted-ted[now];
		now=par[now];
		unnow++;
	}
	allted=fted;
	int resa=(int)pq.size();
	now=had;
	int fn=0;
	while(now!=t){
		for(int i=0;i<(int)alldp[now].size()-(val[now]-fn);i++){
			int x=alldp[now][i]+allted-1;
		//	cout<<now<<" asd "<<x<<"\n";
			resa=max(resa,x+fn);
		}
		allted-=ted[now];
		fn=val[now];
		val[par[now]]+=val[now];
		now=par[now];
	}
	mainres=resa;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>t>>m;
	for(int i=0;i<n-1;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	vis[m]=1;
	dfs(t);
	solve(m);
	cout<<mainres<<"\n";
}

Compilation message

mousetrap.cpp: In function 'void dfs(int, int)':
mousetrap.cpp:43:8: warning: unused variable 'maxa1' [-Wunused-variable]
   43 |    int maxa1=alldp[u].back(),maxa2=alldp[u][(int)alldp[u].size()-2];
      |        ^~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47308 KB Output is correct
2 Correct 22 ms 47300 KB Output is correct
3 Correct 23 ms 47316 KB Output is correct
4 Correct 24 ms 47316 KB Output is correct
5 Correct 27 ms 47264 KB Output is correct
6 Correct 28 ms 47316 KB Output is correct
7 Correct 22 ms 47320 KB Output is correct
8 Correct 26 ms 47236 KB Output is correct
9 Correct 25 ms 47256 KB Output is correct
10 Correct 25 ms 47252 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 110420 KB Output is correct
2 Correct 354 ms 104160 KB Output is correct
3 Correct 858 ms 116088 KB Output is correct
4 Correct 409 ms 82048 KB Output is correct
5 Correct 848 ms 116056 KB Output is correct
6 Correct 883 ms 115880 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47308 KB Output is correct
2 Correct 22 ms 47300 KB Output is correct
3 Correct 23 ms 47316 KB Output is correct
4 Correct 24 ms 47316 KB Output is correct
5 Correct 27 ms 47264 KB Output is correct
6 Correct 28 ms 47316 KB Output is correct
7 Correct 22 ms 47320 KB Output is correct
8 Correct 26 ms 47236 KB Output is correct
9 Correct 25 ms 47256 KB Output is correct
10 Correct 25 ms 47252 KB Output is correct
11 Incorrect 23 ms 47228 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47308 KB Output is correct
2 Correct 22 ms 47300 KB Output is correct
3 Correct 23 ms 47316 KB Output is correct
4 Correct 24 ms 47316 KB Output is correct
5 Correct 27 ms 47264 KB Output is correct
6 Correct 28 ms 47316 KB Output is correct
7 Correct 22 ms 47320 KB Output is correct
8 Correct 26 ms 47236 KB Output is correct
9 Correct 25 ms 47256 KB Output is correct
10 Correct 25 ms 47252 KB Output is correct
11 Correct 323 ms 110420 KB Output is correct
12 Correct 354 ms 104160 KB Output is correct
13 Correct 858 ms 116088 KB Output is correct
14 Correct 409 ms 82048 KB Output is correct
15 Correct 848 ms 116056 KB Output is correct
16 Correct 883 ms 115880 KB Output is correct
17 Incorrect 23 ms 47228 KB Output isn't correct
18 Halted 0 ms 0 KB -