oj.uz

Submission #827798

# Submission time Handle Problem Language Result Execution time Memory
827798 2023-08-16T19:01:51 Z EthanKim8683 Hard route (IZhO17_road) C++17
0 / 100
 7 ms 12084 KB 
#include<bits/stdc++.h>
using namespace std;
using I=int;
using Lli=long long int;
const I N=500000;
vector<I>adjs[N];
I dp1[N],dp2[N];
vector<I>curs;
I cnts[N];
pair<Lli,Lli>res={0,1};
void dfs1(I a,I p=-1){
  for(auto b:adjs[a])if(b!=p){
    dfs1(b,a);
    dp1[a]=max(dp1[a],dp1[b]+1);
  }
}
void dfs2(I a,I p=-1){
  I low=dp2[a];
  for(auto b:adjs[a])if(b!=p){
    dp2[b]=max(dp2[b],low+1);
    low=max(low,dp1[b]+1);
  }
  reverse(adjs[a].begin(),adjs[a].end());
  low=dp2[a];
  for(auto b:adjs[a])if(b!=p){
    dp2[b]=max(dp2[b],low+1);
    low=max(low,dp1[b]+1);
  }
  curs.clear(),curs.push_back(dp2[a]);
  for(auto b:adjs[a])if(b!=p)curs.push_back(dp1[b]+1);
  if(curs.size()>=3){
    sort(curs.rbegin(),curs.rend());
    Lli x=curs[0],y=curs[1],z=curs[2];
    for(auto i:curs)cnts[i]++;
    Lli val=x*(y+z),cnt=1;
    cnt*=cnts[x];
    cnt*=cnts[y]-(y==x);
    cnt*=cnts[z]-(z==x)-(z==y);
    if(y==z)cnt/=2;
    if(val>res.first)res={val,0};
    if(val==res.first)res.second+=cnt;
    for(auto i:curs)cnts[i]--;
  }
  for(auto b:adjs[a])if(b!=p)dfs2(b,a);
}
I main(){
  cin.tie(0)->sync_with_stdio(0);
  I n;cin>>n;
  for(I i=0;i<n-1;i++){
    I u,v;cin>>u>>v,u--,v--;
    adjs[u].push_back(v);
    adjs[v].push_back(u);
  }
  dfs1(0),dfs2(0);
  auto[val,cnt]=res;
  printf("%lli %lli\n",val,cnt);
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11976 KB Output is correct
3 Correct 7 ms 12036 KB Output is correct
4 Incorrect 7 ms 12084 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11976 KB Output is correct
3 Correct 7 ms 12036 KB Output is correct
4 Incorrect 7 ms 12084 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11976 KB Output is correct
3 Correct 7 ms 12036 KB Output is correct
4 Incorrect 7 ms 12084 KB Output isn't correct
5 Halted 0 ms 0 KB -