Submission #899431

#	Time	Username	Problem	Language	Result	Execution time	Memory
899431		TAhmed33	Hard route (IZhO17_road)	C++98	0 / 100	7 ms	23900 KiB

road

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
using namespace std;
const int MAXN = 5e5 + 25;
vector <int> adj[MAXN];
vector <int> dp[MAXN];
int n;
int mx = 0, cnt = 0;
void upd (int x) {
	if (x > mx) {
		mx = x; cnt = 1;
	} else if (x == mx) cnt++;
}
void dfs (int pos, int par, int dep = 0) {
	dp[pos].clear();
	if (adj[pos].size() == 1 && par != -1) {
		dp[pos].push_back(0);
		upd(0);
		return;
	}
	for (auto j : adj[pos]) {
		if (j == par) continue;
		dfs(j, pos, dep + 1);
		for (auto i : dp[j]) {
			dp[pos].push_back(i + 1);
		}
	}
	sort(dp[pos].begin(), dp[pos].end());
	reverse(dp[pos].begin(), dp[pos].end());
	if (dp[pos].size() > 1) {
		upd((dep + dp[pos][0]) * dp[pos][1]);
		upd((dep + dp[pos][1]) * dp[pos][0]);
	}
	//cout << pos << " " << par << " " << dep << ": "; for (auto j : dp[pos]) cout << j << " ";
	//cout << '\n';
	dp[pos].resize(1);
}	
int main () {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for (int i = 1; i <= n; i++) {
		if (adj[i].size() == 1) {
			//cout << "            " << i << ": \n";
			dfs(i, -1);
		}
	}
	cout << mx << " " << cnt / 2 << '\n';
}

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