제출 #1174795

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1174795		guilhermecpp	Hard route (IZhO17_road)	C++20	0 / 100	6 ms	12104 KiB

road

#include <bits/stdc++.h>
using namespace std;
 
#define N 500010
#define M 4
#define INF 1000000010
#define fi first
#define se second
#define pb push_back
 
typedef long long ll;
typedef pair< ll, ll > pll;
typedef vector< ll > vl;
typedef vector< pll > vll;

ll n;
vl grafo[N];

pll invalid = {0, 0};
pll fart[N][M+1];

pll aux[N][M+1];

pll dp[N];

void Add(ll u, ll val)
{

	for(ll i = 1;i <= M;i++)
	{
	
		if(fart[u][i].fi != val) continue;

		fart[u][i].se++;
		return;

	}

	if(fart[u][M].fi < val) fart[u][M] = {val, 1LL};

	sort(fart[u] + 1, fart[u] + M + 1, greater< pll >());

	return;

}

void Rem(ll u, ll val)
{

	for(ll i = 1;i <= M;i++)
	{
	
		if(fart[u][i].fi != val) continue;
		
		fart[u][i].se--;
		if(fart[u][i].se != 0) return;

		fart[u][i] = invalid;
		break;

	}

	sort(fart[u] + 1, fart[u] + M + 1, greater< pll >());

	return;

}

void Copy(pll *a, pll *b)
{

	for(ll i = 1;i <= M;i++) b[i] = a[i];
	return;

}

pll Calc(pll *vet)
{

	if(vet[1].se + vet[2].se + vet[3].se < 3) return invalid;

	ll a, b;

	if(vet[1].se >= 3) 
	{
		
		a = vet[1].fi * (vet[1].fi + vet[1].fi);
		b = (vet[1].se * (vet[1].se - 1)) / 2;

	}else if(vet[1].se == 2)
	{
		
		a = vet[1].fi * (vet[1].fi + vet[2].fi);
		b = vet[1].se * vet[2].se;

	}else if(vet[2].se >= 2)
	{
		
		a = vet[1].fi * (vet[2].fi + vet[2].fi);
		b = (vet[2].se * (vet[2].se - 1)) / 2;

	}else
	{
		
		a = vet[1].fi * (vet[2].fi + vet[3].fi);
		b = vet[2].se * vet[3].se;

	}

	return {a, b};

}

void DFS(ll u, ll pai)
{

	for(ll i = 1;i <= M;i++) fart[u][i] = invalid;

	for(auto v : grafo[u])
	{

		if(v == pai) continue;

		DFS(v, u);

		Add(u, fart[v][1].fi+1);
		
	}

	return;

}

void Solv(ll u, ll pai)
{

	dp[u] = Calc(fart[u]);

	Copy(fart[u], aux[u]);

	for(auto v : grafo[u])
	{

		if(v == pai) continue;

		Rem(u, fart[v][1].fi+1);

		if((fart[u][1].fi != u) || (fart[u][1].se == 1))	
		{
			
			Add(v, fart[u][1].fi+1);
		
		}else
		{
			
			Add(v, fart[u][2].fi+1);

		}

		Solv(v, u);

		Copy(aux[u], fart[u]);

	}

	return;

}

int main()
{
 
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

	ll u, v, i;

	cin >> n;

	for(i = 1;i < n;i++)
	{

		cin >> u >> v;

		grafo[u].pb(v);
		grafo[v].pb(u);

	}

	DFS(1, 1);
	Solv(1, 1);

	sort(dp + 1, dp + n + 1, greater< pll >());
	dp[n+1] = {-1, -1};

	i = 2;
	while(dp[i].fi == dp[1].fi) dp[1].se += dp[i++].se;

	if(dp[1].se == 0) dp[1].se = 1;

	cout << dp[1].fi << " " << dp[1].se << endl;

    return 0;
 
} 

• Subtask 1: 0 / 19
• Subtask 2: 0 / 33
• Subtask 3: 0 / 48