Submission #173306

#	Time	Username	Problem	Language	Result	Execution time	Memory
173306		MvC	Hard route (IZhO17_road)	C++11	52 / 100	785 ms	62712 KiB

road

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=5e3+50;
const int mod=1e9+7;
using namespace std;
int n,i,j,t,u,v,x,y,p,mx,mxl[nmax],lvl[nmax],pr[nmax],rs,cur,cnt,nr,c,ps[nmax][nmax];
vector<int>a[nmax],lf;
vector<pair<int,int> >d[nmax];
vector<vector<pair<int,int> > >lv[nmax];
void bas(int x,int p,int l)
{
	pr[x]=p;
	lvl[x]=mxl[x]=l;
	for(int i=0;i<(int)a[x].size();i++)
	{
		int y=a[x][i];
		if(y==p)continue;
		bas(y,x,l+1);
		mxl[x]=max(mxl[x],mxl[y]);
		d[x].pb(mkp(mxl[y]-lvl[x],y));
	}
}
void dis(int x,int p,int l)
{
	mx=max(mx,l);
	for(int i=0;i<(int)a[x].size();i++)
	{
		int y=a[x][i];
		if(y==p)continue;
		dis(y,x,l+1);
	}
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n;
	for(i=1;i<n;i++)
	{
		cin>>x>>y;
		a[x].pb(y);
		a[y].pb(x);
		ps[x][y]=(int)a[x].size()-1;
		ps[y][x]=(int)a[y].size()-1;
	}
	for(i=1;i<=n;i++)lv[i].resize((int)a[i].size()+3);
	bas(1,0,0);
	for(i=2;i<=n;i++)
	{
		mx=0;
		dis(pr[i],i,0);
		d[i].pb(mkp(mx+1,pr[i]));
		if((int)a[i].size()==1)lf.pb(i);
	}
	for(i=1;i<=n;i++)
	{
		sort(d[i].begin(),d[i].end());
		reverse(d[i].begin(),d[i].end());
	}
	for(i=0;i<(int)lf.size();i++)
	{
		x=lf[i],mx=0,nr=0,c=0;
		while(x)
		{
			lv[x][ps[x][c]].pb(mkp(nr,mx));
			cur=-1;
			for(j=0;j<(int)d[x].size();j++)
			{
				if(d[x][j].sc!=c && d[x][j].sc!=pr[x])
				{
					cur=d[x][j].fr;
					break;
				}
			}
			if(cur!=-1)mx=max(mx,cur);
			c=x,x=pr[x],nr++;
		}
	}
	for(i=1;i<=n;i++)
	{
		for(j=0;j<(int)a[i].size();j++)
		{
			x=a[i][j];
			if(x==pr[i])continue;
			for(t=j+1;t<(int)a[i].size();t++)
			{
				y=a[i][t];
				if(y==pr[i])continue;
				mx=0;
				for(p=0;p<(int)d[i].size();p++)
				{
					if(d[i][p].sc!=x && d[i][p].sc!=y)
					{
						mx=d[i][p].fr;
						break;
					}
				}
				for(u=0;u<(int)lv[i][ps[i][x]].size();u++)
				{
					for(v=0;v<(int)lv[i][ps[i][y]].size();v++)
					{
						cur=max(mx,max(lv[i][ps[i][x]][u].sc,lv[i][ps[i][y]][v].sc))*(lv[i][ps[i][x]][u].fr+lv[i][ps[i][y]][v].fr);
						if(rs==cur)cnt++;
						else if(rs<cur)rs=cur,cnt=1;
					}
				}
			}
		}
	}
	if((int)a[1].size()==1)
	{
		for(i=0;i<(int)a[1].size();i++)
		{
			x=a[1][i];
			for(j=0;j<(int)lv[1][ps[1][x]].size();j++)
			{
				cur=lv[1][ps[1][x]][j].fr*lv[1][ps[1][x]][j].sc;
				if(rs==cur)cnt++;
				else if(rs<cur)rs=cur,cnt=1;
			}
		}
	}
	cout<<rs<<" "<<cnt<<endl;
	return 0;
}

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