oj.uz

Submission #463617

# Submission time Handle Problem Language Result Execution time Memory
463617 2021-08-11T11:16:32 Z vanic Mousetrap (CEOI17_mousetrap) C++14
20 / 100
 1041 ms 87540 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;
	int maksi, ind;
	for(int i=0; i<uk; i++){
		token++;
		while(token){
			maksi=0;
			ind=-1;
			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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47172 KB Output is correct
2 Correct 25 ms 47252 KB Output is correct
3 Correct 25 ms 47212 KB Output is correct
4 Correct 25 ms 47264 KB Output is correct
5 Correct 25 ms 47212 KB Output is correct
6 Correct 25 ms 47152 KB Output is correct
7 Correct 25 ms 47208 KB Output is correct
8 Correct 26 ms 47196 KB Output is correct
9 Correct 27 ms 47248 KB Output is correct
10 Correct 25 ms 47180 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 86372 KB Output is correct
2 Correct 359 ms 82364 KB Output is correct
3 Correct 953 ms 87540 KB Output is correct
4 Correct 449 ms 67380 KB Output is correct
5 Correct 1026 ms 87440 KB Output is correct
6 Incorrect 1041 ms 87432 KB Output isn't correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47172 KB Output is correct
2 Correct 25 ms 47252 KB Output is correct
3 Correct 25 ms 47212 KB Output is correct
4 Correct 25 ms 47264 KB Output is correct
5 Correct 25 ms 47212 KB Output is correct
6 Correct 25 ms 47152 KB Output is correct
7 Correct 25 ms 47208 KB Output is correct
8 Correct 26 ms 47196 KB Output is correct
9 Correct 27 ms 47248 KB Output is correct
10 Correct 25 ms 47180 KB Output is correct
11 Correct 27 ms 47272 KB Output is correct
12 Correct 27 ms 47380 KB Output is correct
13 Correct 26 ms 47284 KB Output is correct
14 Correct 28 ms 47312 KB Output is correct
15 Correct 26 ms 47304 KB Output is correct
16 Incorrect 27 ms 47300 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47172 KB Output is correct
2 Correct 25 ms 47252 KB Output is correct
3 Correct 25 ms 47212 KB Output is correct
4 Correct 25 ms 47264 KB Output is correct
5 Correct 25 ms 47212 KB Output is correct
6 Correct 25 ms 47152 KB Output is correct
7 Correct 25 ms 47208 KB Output is correct
8 Correct 26 ms 47196 KB Output is correct
9 Correct 27 ms 47248 KB Output is correct
10 Correct 25 ms 47180 KB Output is correct
11 Correct 396 ms 86372 KB Output is correct
12 Correct 359 ms 82364 KB Output is correct
13 Correct 953 ms 87540 KB Output is correct
14 Correct 449 ms 67380 KB Output is correct
15 Correct 1026 ms 87440 KB Output is correct
16 Incorrect 1041 ms 87432 KB Output isn't correct