oj.uz

Submission #463626

# Submission time Handle Problem Language Result Execution time Memory
463626 2021-08-11T11:39:29 Z vanic Mousetrap (CEOI17_mousetrap) C++14
45 / 100
 1022 ms 87532 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];
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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47192 KB Output is correct
2 Correct 26 ms 47276 KB Output is correct
3 Correct 27 ms 47184 KB Output is correct
4 Correct 25 ms 47204 KB Output is correct
5 Correct 26 ms 47200 KB Output is correct
6 Correct 25 ms 47280 KB Output is correct
7 Correct 26 ms 47224 KB Output is correct
8 Correct 25 ms 47208 KB Output is correct
9 Correct 25 ms 47244 KB Output is correct
10 Correct 26 ms 47264 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 86404 KB Output is correct
2 Correct 360 ms 82480 KB Output is correct
3 Correct 1022 ms 87408 KB Output is correct
4 Correct 462 ms 67488 KB Output is correct
5 Correct 971 ms 87508 KB Output is correct
6 Correct 1002 ms 87532 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47192 KB Output is correct
2 Correct 26 ms 47276 KB Output is correct
3 Correct 27 ms 47184 KB Output is correct
4 Correct 25 ms 47204 KB Output is correct
5 Correct 26 ms 47200 KB Output is correct
6 Correct 25 ms 47280 KB Output is correct
7 Correct 26 ms 47224 KB Output is correct
8 Correct 25 ms 47208 KB Output is correct
9 Correct 25 ms 47244 KB Output is correct
10 Correct 26 ms 47264 KB Output is correct
11 Correct 26 ms 47284 KB Output is correct
12 Correct 26 ms 47300 KB Output is correct
13 Correct 25 ms 47248 KB Output is correct
14 Correct 27 ms 47308 KB Output is correct
15 Correct 27 ms 47340 KB Output is correct
16 Incorrect 26 ms 47308 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47192 KB Output is correct
2 Correct 26 ms 47276 KB Output is correct
3 Correct 27 ms 47184 KB Output is correct
4 Correct 25 ms 47204 KB Output is correct
5 Correct 26 ms 47200 KB Output is correct
6 Correct 25 ms 47280 KB Output is correct
7 Correct 26 ms 47224 KB Output is correct
8 Correct 25 ms 47208 KB Output is correct
9 Correct 25 ms 47244 KB Output is correct
10 Correct 26 ms 47264 KB Output is correct
11 Correct 412 ms 86404 KB Output is correct
12 Correct 360 ms 82480 KB Output is correct
13 Correct 1022 ms 87408 KB Output is correct
14 Correct 462 ms 67488 KB Output is correct
15 Correct 971 ms 87508 KB Output is correct
16 Correct 1002 ms 87532 KB Output is correct
17 Correct 26 ms 47284 KB Output is correct
18 Correct 26 ms 47300 KB Output is correct
19 Correct 25 ms 47248 KB Output is correct
20 Correct 27 ms 47308 KB Output is correct
21 Correct 27 ms 47340 KB Output is correct
22 Incorrect 26 ms 47308 KB Output isn't correct
23 Halted 0 ms 0 KB -