Submission #960803

#	Time	Username	Problem	Language	Result	Execution time	Memory
960803		Trisanu_Das	Hard route (IZhO17_road)	C++17	52 / 100	284 ms	1116 KiB

road

#include <bits/stdc++.h>
using namespace std;
 
const int NM = 5000;
 
int N, deg[NM+5], f[NM+5], g[NM+5], dep[NM+5];
vector <int> adj[NM+5];
int ans = -1, cnt = -1;
 
void dfs(int u, int p){
	dep[u] = (p == -1 ? 0 : dep[p]+1);
	f[u] = g[u] = 0;
	for (int v : adj[u]){
		if (v == p) continue;
		dfs(v, u);
		if (f[v]+1 > f[u]){
			g[u] = f[u];
			f[u] = f[v]+1;
		}
		else if (f[v]+1 > g[u]) g[u] = f[v]+1;
	}
}
 
void calc(int u, int p, int cur){
	bool has_child = 0;
	for (int v : adj[u]){
		if (v == p) continue;
		has_child = 1;
		if (f[v]+1 == f[u]) calc(v, u, max(cur, g[u]));
		else calc(v, u, max(cur, f[u]));
	}
	if (!has_child){
		if (dep[u]*cur > ans){
			ans = dep[u]*cur;
			cnt = 1;
		}
		else if (dep[u]*cur == ans) cnt++;
	}
}
 
void solve(int r){
	dfs(r, -1);
	calc(r, -1, 0);
}
 
int main(){
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	cin >> N;
	for (int i = 1; i < N; i++){
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		deg[u]++; deg[v]++;
	}
	for (int i = 1; i <= N; i++) if (deg[i] == 1) solve(i);
	cout << ans << ' ' << cnt / 2;
}

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