Submission #731082

#	Time	Username	Problem	Language	Result	Execution time	Memory
731082		beaboss	Hard route (IZhO17_road)	C++14	0 / 100	4 ms	5000 KiB

road

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;

const ll INF = 1e17 + 10ll;
const ll N = 2*1e5 + 10;
int n;
vector<int> adj[N];
int maxoutdist[N];
int out[N];
int maxi = 0;
int nummaxi = 0;
int h[N];

void update(int ans, int numways) {
	if (ans > maxi) {
		maxi = ans;
		nummaxi = numways;
	} else if (ans == maxi) nummaxi += numways;
}

void dfs1(int cur, int p) {
	vector<int> heights;
	map<int, int> cntheights;
	for (auto val: adj[cur]) {
		if (val != p) {
			heights.pb(h[val] + 1);
			cntheights[h[val] + 1]++;
		}
	}


	heights.pb(out[cur]);
	cntheights[out[cur]]++;

	sort(heights.rbegin(), heights.rend());

	// cout << cur << heights[0] << heights[1] << heights[2] << endl;
	if (heights.size() >= 3) {
		int numways = 1;
		numways *= cntheights[heights[0]];
		cntheights[heights[0]]--;
		if (heights[1]==heights[2]) numways *= (cntheights[heights[1]] * (cntheights[heights[1]] - 1)/2);
		else numways *= (cntheights[heights[1]] * (cntheights[heights[2]]));

		update(heights[0] * (heights[1] + heights[2]), numways);

	}

	for (auto val: adj[cur]) {
		if (val != p) dfs1(val, cur);
	}
}

void dfs0(int cur, int p) {
	// cout << cur << endl;
	vector<int> heights ={0, 0, 0};
	for (auto val: adj[cur]) if (val != p) heights.pb(h[val] + 2);

	sort(heights.rbegin(), heights.rend());

	for (auto val: adj[cur]) {
		if (val != p) {
			int curopt = heights[0];
			if (h[val] + 2 == curopt) curopt = heights[1];
			if (curopt < out[cur] + 1) {
				curopt = out[cur]+1;
			}
			out[val] = max(out[val], curopt);
			dfs0(val, cur);
		}
	}

	// cout << cur << out[cur] << endl;

}


void dfs(int cur, int p) { // get all heights
	vector<int> heights;
	map<int, int> cntheights;
	for (auto val: adj[cur]) {
		if (val != p) {
			dfs(val, cur);
			h[cur] = max(h[val] + 1, h[cur]);
		}
	}

}


int main() {
	

	cin >> n;

	for (ll i = 0; i < n -1; i++ ) {
		ll a, b;
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);

	}
	dfs(1, -1);
	dfs0(1, -1);
	dfs1(1, -1);
	if (maxi == 0) nummaxi = 1;
	cout << maxi << ' ' << nummaxi << endl;



	
}

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