oj.uz

Submission #173096

# Submission time Handle Problem Language Result Execution time Memory
173096 2020-01-03T11:03:42 Z MvC Hard route (IZhO17_road) C++11
0 / 100
 11 ms 7544 KB 
#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=5e2+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;
vector<int>a[nmax],lf;
vector<pair<int,int> >lv[nmax][nmax],d[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);
	}
	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][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][x].size();u++)
				{
					for(v=0;v<(int)lv[i][y].size();v++)
					{
						cur=max(mx,max(lv[i][x][u].sc,lv[i][y][u].sc))*(lv[i][x][u].fr+lv[i][y][u].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][x].size();j++)
			{
				cur=lv[1][x][j].fr*lv[1][x][j].sc;
				if(rs==cur)cnt++;
				else if(rs<cur)rs=cur,cnt=1;
			}
		}
	}
	cout<<rs<<" "<<cnt<<endl;
	return 0;
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7544 KB Output is correct
2 Correct 11 ms 7544 KB Output is correct
3 Correct 9 ms 7544 KB Output is correct
4 Correct 9 ms 7544 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 9 ms 7544 KB Output is correct
7 Incorrect 11 ms 7516 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7544 KB Output is correct
2 Correct 11 ms 7544 KB Output is correct
3 Correct 9 ms 7544 KB Output is correct
4 Correct 9 ms 7544 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 9 ms 7544 KB Output is correct
7 Incorrect 11 ms 7516 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7544 KB Output is correct
2 Correct 11 ms 7544 KB Output is correct
3 Correct 9 ms 7544 KB Output is correct
4 Correct 9 ms 7544 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 9 ms 7544 KB Output is correct
7 Incorrect 11 ms 7516 KB Output isn't correct
8 Halted 0 ms 0 KB -