Submission #334034

#	Time	Username	Problem	Language	Result	Execution time	Memory
334034		tengiz05	Hard route (IZhO17_road)	C++17	19 / 100	2069 ms	25324 KiB

road

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
const int mod = 1e9+7, N = 5e5+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val);}
int n, m, k;
vector<int> edges[N];
int up[N][20];
int tin[N], tout[N], d[N];
int timer=0;
vector<pii> V[N];
void dfs(int u, int p, int dist=0){
	d[u] = dist;
	tin[u] = timer++;
	up[u][0] = p;
	for(int i=1;i<20;i++){
		up[u][i] = up[up[u][i-1]][i-1];
	}
	for(auto v : edges[u]){
		if(v != p)dfs(v, u, dist+1);
	}
	tout[u] = timer++;
}
bool isancestor(int u, int v){
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v){
	if(isancestor(u,v))return u;
	if(isancestor(v,u))return v;
	for(int i=19;i>=0;i--){
		if(!isancestor(up[u][i], v))u = up[u][i];
	}
	return up[u][0];
}
int dist(int u, int v){
	int l = lca(u, v);
	int res = d[u]+d[v]-(d[l]*2);
	return res;
}
int find_max(int u, int p, int dist=0){
	int mx = dist;
	for(auto v : edges[u]){
		if(v != p)mx = max(mx, find_max(v, u, dist+1));
	}return mx;
}
int ans=0, cnt=0;
int pre[N];
void precompute(int u, int p){
	if(u != p)pre[u] = find_max(p, u, 1);
	for(auto v : edges[u]){
		if(v != p)precompute(v, u);
	}
}
void solve(int test_case){
	int i, j;
	cin >> n;
	for(i=1;i<n;i++){
		int u, v;
		cin >> u >> v;
		edges[u].pb(v);
		edges[v].pb(u);
	}
	dfs(1, 1);
	vector<int> leaves;
	for(i=1;i<=n;i++){
		if(edges[i].size() == 1)leaves.pb(i);
	}
	precompute(1,1);
	int sz = leaves.size();
	for(i=0;i<sz;i++){
		for(j=i+1;j<sz;j++){
			int u = leaves[i], v = leaves[j];
			int fs = dist(u,v);
			int par = pre[lca(u,v)];
		//	cout << fs << ' ' << par << '\n';
			for(k=0;k<sz;k++){
				if(k == i || k == j)continue;
				int t = leaves[k];
				int mn = min(dist(t,u)-d[u]+d[lca(t,u)], dist(t, v)-d[v]+d[lca(t,v)]);
				if(mn > par)par = mn;
			}
		//	cout << fs << ' ' << par << '\n';
			if(fs*par > ans){
				ans = fs*par;
				cnt = 1;
			}else if(fs*par == ans)cnt++;
		}
	}cout << ans << ' ' << cnt << '\n';
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int ___T;
	cin >> ___T;
	for(int T_CASE = 1; T_CASE <= ___T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

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