| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 173095 |
2020-01-03T11:02:55 Z |
MvC |
Hard route (IZhO17_road) |
C++11 |
|
215 ms |
262148 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=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;
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
215 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
215 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
215 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
