oj.uz

Submission #704579

# Submission time Handle Problem Language Result Execution time Memory
704579 2023-03-02T10:36:05 Z amirhoseinfar1385 Mousetrap (CEOI17_mousetrap) C++17
0 / 100
 343 ms 119372 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;
priority_queue<pair<int,int>>pq;
int val[maxn];

void dfs(int u,int para=0){
	par[u]=para;
	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){
		for(int i=(int)alldp[now].size()-1;i>=0;i--){
			int x=alldp[now][i]+allted-1;
			if((int)pq.size()<unnow){
				pq.push(make_pair(-x,now));
				val[now]++;
			}
			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-=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:28:8: warning: unused variable 'maxa1' [-Wunused-variable]
   28 |    int maxa1=alldp[u].back(),maxa2=alldp[u][(int)alldp[u].size()-2];
      |        ^~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47236 KB Output is correct
2 Correct 27 ms 47312 KB Output is correct
3 Correct 22 ms 47316 KB Output is correct
4 Correct 23 ms 47288 KB Output is correct
5 Correct 23 ms 47188 KB Output is correct
6 Correct 23 ms 47316 KB Output is correct
7 Incorrect 23 ms 47284 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47236 KB Output is correct
2 Correct 27 ms 47312 KB Output is correct
3 Correct 22 ms 47316 KB Output is correct
4 Correct 23 ms 47288 KB Output is correct
5 Correct 23 ms 47188 KB Output is correct
6 Correct 23 ms 47316 KB Output is correct
7 Incorrect 23 ms 47284 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47236 KB Output is correct
2 Correct 27 ms 47312 KB Output is correct
3 Correct 22 ms 47316 KB Output is correct
4 Correct 23 ms 47288 KB Output is correct
5 Correct 23 ms 47188 KB Output is correct
6 Correct 23 ms 47316 KB Output is correct
7 Incorrect 23 ms 47284 KB Output isn't correct
8 Halted 0 ms 0 KB -