Submission #485969

#	Time	Username	Problem	Language	Result	Execution time	Memory
485969		MilosMilutinovic	Hard route (IZhO17_road)	C++14	0 / 100	21 ms	12108 KiB

road

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
const ll mod2=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=501000;
int n,p[N][20],dep[N],mx[N];
VI e[N],dn;

void dfs(int u,int f) {
	dep[u]=dep[f]+1;
	p[u][0]=f;
	mx[u]=dep[u];
	bool lf=true;
	for (auto v:e[u]) {
		if (v==f) continue;
		lf=false;
		dfs(v,u);
		mx[u]=max(mx[u],mx[v]);
	} 
	if (lf) dn.pb(u);
}

#define LOGN 20
int lca(int u,int v) {
	if (dep[u]>dep[v]) swap(u,v);
	per(i,0,LOGN) if (dep[p[v][i]]>=dep[u]) v=p[v][i];
	if (u==v) return u;
	per(i,0,LOGN) if (p[u][i]!=p[v][i]) u=p[u][i],v=p[v][i];
	return p[u][0];
}

int dist(int u,int v) {
	return dep[u]+dep[v]-2*dep[lca(u,v)];
}

ll calc(int u,int v) {
	int l=lca(u,v);
	if (u==l||v==l) return 0;
	ll d=0;
	for (auto x:e[l]) if (lca(u,x)!=x&&lca(v,x)!=x) d=max(d,(ll)mx[x]-dep[l]);
	rep(i,1,n+1) if (lca(i,l)!=l) d=max(d,(ll)dist(i,l));
	return d*dist(u,v);
}

int main() {
	scanf("%d",&n);
	rep(i,1,n) {
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].pb(v); e[v].pb(u);
	}
	int root=-1;
	rep(i,1,n+1) if (SZ(e[i])>1) root=i;
	if (root==-1) {
		printf("0 1");
		return 0;
	}
	dfs(root,0);
	rep(j,1,LOGN) rep(i,1,n+1) p[i][j]=p[p[i][j-1]][j-1];
	ll ans=0; int cnt=0;
	rep(i,0,SZ(dn)-1) {
		rep(j,i+1,SZ(dn)) {
			ll x=calc(dn[i],dn[j]);
			//printf("%d %d  %lld\n",dn[i],dn[j],x);
			if (x==ans) cnt++;
			else if (x>ans) ans=x,cnt=1;
		}
	}
	printf("%lld %d",ans,cnt);
}

Compilation message (stderr)

road.cpp: In function 'int main()':
road.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
road.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   scanf("%d%d",&u,&v);
      |   ~~~~~^~~~~~~~~~~~~~

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