Submission #463626

#	Time	Username	Problem	Language	Result	Execution time	Memory
463626		vanic	Mousetrap (CEOI17_mousetrap)	C++14	45 / 100	1022 ms	87532 KiB

mousetrap

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn=1e6+5;

vector < int > ms[maxn];
int gore[maxn];
int dp[maxn];

void dfs(int x, int prosl){
	dp[x]=ms[x].size()-1;
	int maksi=0, drugi=0;
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]!=prosl){
			dfs(ms[x][i], x);
			if(dp[ms[x][i]]>maksi){
				drugi=maksi;
				maksi=dp[ms[x][i]];
			}
			else if(dp[ms[x][i]]>drugi){
				drugi=dp[ms[x][i]];
			}
		}
	}
	dp[x]+=drugi;
}

void rokaj(int x, int prosl){
	gore[x]=prosl;
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]!=prosl){
			rokaj(ms[x][i], x);
		}
	}
}


vector < int > val[maxn];

int main(){
	int n, t, m;
	scanf("%d%d%d", &n, &t, &m);
	t--;
	m--;
	int a, b;
	for(int i=0; i<n-1; i++){
		scanf("%d%d", &a, &b);
		a--;
		b--;
		ms[a].push_back(b);
		ms[b].push_back(a);
	}
	if(t==m){
		printf("0\n");
		return 0;
	}
	rokaj(t, t);
	dfs(t, t);
	int sol=0;
	int x=m;
	int prosl=m;
	int sad=0;
	int svi=0;
	while(gore[x]!=x){
		for(int i=0; i<(int)ms[x].size(); i++){
			if(ms[x][i]!=gore[x] && ms[x][i]!=prosl){
				svi++;
				val[sad].push_back(dp[ms[x][i]]);
			}
		}
		sad++;
		prosl=x;
		x=gore[x];
	}
	int uk=sad;
	for(int i=0; i<uk; i++){
		sort(val[i].begin(), val[i].end());
	}
	x=m;
	int token=0;
	int maksi, ind;
	for(int i=0; i<uk; i++){
		token++;
		while(token){
			maksi=-1;
			ind=-1;
			for(int j=i; j<uk; j++){
				if((int)val[j].size()>j-i){
					if(maksi<=val[j][val[j].size()-(j-i+1)]){
						maksi=val[j][val[j].size()-(j-i+1)];
						ind=j;
					}
				}
			}
			if(ind==-1){
				break;
			}
			else{
				val[ind].pop_back();
				token--;
			}
		}
		if(!val[i].empty()){
			sol=max(sol, val[i].back()+svi);
			svi-=val[i].size();
		}
	}
	if(!sol){
		sol=svi;
	}
	printf("%d\n", sol);
	return 0;
}

Compilation message (stderr)

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%d%d%d", &n, &t, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35