oj.uz

Submission #463616

# Submission time Handle Problem Language Result Execution time Memory
463616 2021-08-11T11:15:25 Z vanic Mousetrap (CEOI17_mousetrap) C++14
0 / 100
 1035 ms 87524 KB 
#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];
//bool bio[maxn];
int dp[maxn];

void dfs(int x, int prosl){
	int br=0;
/*	for(int i=0; i<(int)ms[x].size(); i++){
		if(bio[ms[x][i]]){
			br++;
		}
	}*/
	dp[x]=ms[x].size()-1-br;
	int maksi=0, drugi=0;
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]!=prosl){// && !bio[ms[x][i]]){
			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]];
			}
		}
	}
//	bio[x]=1;
	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;
	for(int i=0; i<uk; i++){
		int maksi=0, ind=-1;
		token++;
		while(token){
			for(int j=i; j<uk; j++){
				if((int)val[j].size()>j-i){
					if(maksi<val[j][j-i]){
						maksi=val[j][j-i];
						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

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

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47180 KB Output is correct
2 Correct 27 ms 47220 KB Output is correct
3 Correct 25 ms 47248 KB Output is correct
4 Correct 25 ms 47188 KB Output is correct
5 Correct 25 ms 47208 KB Output is correct
6 Incorrect 25 ms 47180 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 86388 KB Output is correct
2 Correct 360 ms 82352 KB Output is correct
3 Correct 999 ms 87524 KB Output is correct
4 Correct 503 ms 67348 KB Output is correct
5 Correct 1035 ms 87452 KB Output is correct
6 Incorrect 975 ms 87480 KB Output isn't correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47180 KB Output is correct
2 Correct 27 ms 47220 KB Output is correct
3 Correct 25 ms 47248 KB Output is correct
4 Correct 25 ms 47188 KB Output is correct
5 Correct 25 ms 47208 KB Output is correct
6 Incorrect 25 ms 47180 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47180 KB Output is correct
2 Correct 27 ms 47220 KB Output is correct
3 Correct 25 ms 47248 KB Output is correct
4 Correct 25 ms 47188 KB Output is correct
5 Correct 25 ms 47208 KB Output is correct
6 Incorrect 25 ms 47180 KB Output isn't correct
7 Halted 0 ms 0 KB -