제출 #1174831

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1174831		guilhermecpp	Hard route (IZhO17_road)	C++20	100 / 100	793 ms	246560 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;

struct Tipo
{

	ll d, f, q, s;

	void operator = (Tipo a)
	{

		d = a.d;
		q = a.q;
		s = a.s;
		f = a.f;

		return;

	}

	bool operator < (Tipo a) const
	{

		if(d != a.d) return d < a.d;
		if(f != a.f) return f < a.f;
		if(q != a.q) return q < a.q;
		return s < a.s;

	}

	bool operator > (Tipo a) const
	{

		if(d != a.d) return d > a.d;
		if(f != a.f) return f > a.f;
		if(q != a.q) return q > a.q;
		return s > a.s;

	}

};

ll n;
vl grafo[N];

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

Tipo aux[N][M+1];

pll dp[N];

void Add(ll u, ll d, ll q)
{

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

		fart[u][i].s += q * fart[u][i].q;
		fart[u][i].q += q; 
		fart[u][i].f += 1LL;

		return;

	}

	if(fart[u][M].d < d) fart[u][M] = {d, 1LL, q, 0LL};

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

	return;

}

void Rem(ll u, ll d, ll q)
{

	if(fart[u][M].d > d) return;

	for(ll i = 1;i <= M;i++)
	{
	
		if(fart[u][i].d != d) continue;
		
		fart[u][i].f -= 1LL;
		fart[u][i].q -= q;
		fart[u][i].s -= q * fart[u][i].q;
		
		if(fart[u][i].f != 0) return;

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

	}

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

	return;

}

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

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

}

pll Calc(Tipo *vet)
{

	if(vet[1].f+vet[2].f+vet[3].f < 3) return {0LL, 0LL};

	ll a, b;

	if(vet[1].f >= 3) 
	{
		
		a = vet[1].d * (vet[1].d + vet[1].d);
		b = vet[1].s;

	}else if(vet[1].f == 2)
	{
		
		a = vet[1].d * (vet[1].d + vet[2].d);
		b = vet[1].q * vet[2].q;

	}else if(vet[2].f >= 2)
	{
		
		a = vet[1].d * (vet[2].d + vet[2].d);
		b = vet[2].s;

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

	}

	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].d+1, fart[v][1].q);
		
	}

	if((ll)(grafo[u].size()) == 1) Add(u, 0, 1);

	// cout << u << endl;

	// for(ll i = 1;i <= M;i++)
	// {
			
	// 	cout << fart[u][i].d << " ";
	// 	cout << fart[u][i].f << " ";
	// 	cout << fart[u][i].q << " ";
	// 	cout << fart[u][i].s << "      ";

	// }

	// cout << endl;
	// cout << endl;
	
	return;

}

void Solv(ll u, ll pai)
{

	// cout << u << endl;

	// for(ll i = 1;i <= M;i++)
	// {
			
	// 	cout << fart[u][i].d << " ";
	// 	cout << fart[u][i].f << " ";
	// 	cout << fart[u][i].q << " ";
	// 	cout << fart[u][i].s << "      ";

	// }

	// cout << endl;
	// cout << endl;

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

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

	for(auto v : grafo[u])
	{

		if(v == pai) continue;

		Rem(u, fart[v][1].d+1, fart[v][1].q);
		Add(v, fart[u][1].d+1, fart[u][1].q);

		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);

	// for(i = 1;i <= n;i++)
	// 	cout << i << " " << dp[i].fi << " " << dp[i].se << endl;

	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: 19 / 19
• Subtask 2: 33 / 33
• Subtask 3: 48 / 48