oj.uz

Submission #463578

# Submission time Handle Problem Language Result Execution time Memory
463578 2021-08-11T10:33:09 Z vanic Mousetrap (CEOI17_mousetrap) C++14
25 / 100
 1022 ms 65092 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);
		}
	}
}

int val[maxn];
int pref[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(n==1){
		printf("0\n");
		return 0;
	}
	rokaj(t, t);
	int sol=0;
	int x=m;
	int br=0;
	while(gore[x]!=x){
		br++;
		x=gore[x];
	}
	x=m;
	int uk=br;
	while(gore[x]!=x){
		br--;
		val[br]=(int)ms[x].size()-2;
		x=gore[x];
	}
	for(int i=0; i<uk; i++){
		pref[i+1]=pref[i]+val[i];
	}
	x=m;
	while(gore[x]!=x){
		dfs(x, gore[x]);
		uk--;
		sol=max(dp[x]+pref[uk], sol);
		x=gore[x];
	}
	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 14 ms 23756 KB Output is correct
2 Correct 13 ms 23768 KB Output is correct
3 Correct 13 ms 23756 KB Output is correct
4 Correct 13 ms 23748 KB Output is correct
5 Incorrect 13 ms 23756 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 63868 KB Output is correct
2 Correct 359 ms 59772 KB Output is correct
3 Correct 987 ms 64884 KB Output is correct
4 Correct 458 ms 44356 KB Output is correct
5 Correct 1002 ms 65064 KB Output is correct
6 Correct 1022 ms 65092 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 13 ms 23768 KB Output is correct
3 Correct 13 ms 23756 KB Output is correct
4 Correct 13 ms 23748 KB Output is correct
5 Incorrect 13 ms 23756 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 13 ms 23768 KB Output is correct
3 Correct 13 ms 23756 KB Output is correct
4 Correct 13 ms 23748 KB Output is correct
5 Incorrect 13 ms 23756 KB Output isn't correct
6 Halted 0 ms 0 KB -