Submission #827895

#	Time	Username	Problem	Language	Result	Execution time	Memory
827895		EthanKim8683	Hard route (IZhO17_road)	C++17	0 / 100	7 ms	12076 KiB

road

#include<bits/stdc++.h>
using namespace std;
using I=int;
using Lli=long long int;
using B=bool;
const I N=500000;
vector<I>adjs[N];
pair<I,I>far;
I pars[N];
vector<I>dias;
B uses[N];
pair<I,I>diss[N];
void dfs1(I a,I p=-1,I d=0){
  far=max(far,{d,a});
  pars[a]=p;
  for(auto b:adjs[a])if(b!=p)dfs1(b,a,d+1);
}
void dfs2(I a,I p=-1){
  if(adjs[a].size()==1)diss[a]={0,1};
  for(auto b:adjs[a])if(b!=p&&!uses[b]){
    dfs2(b,a);
    auto[dis,cnt]=diss[b];dis++;
    if(dis>diss[a].first)diss[a]={dis,0};
    if(dis==diss[a].first)diss[a].second+=cnt;
  }
}
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);
  }
  far={0,0},dfs1(0);
  I x=far.second;
  far={0,x},dfs1(x);
  auto[len,y]=far;
  for(I i=y;i!=-1;i=pars[i])uses[i]=1;
  pair<Lli,Lli>res={0,1};
  for(Lli i=1,j=pars[y];i<len;i++,j=pars[j]){
    dfs2(j);
    auto[dis3,cnt]=diss[j];
    if(!cnt)continue;
    I dis1=i,dis2=len-i;
    if(dis2>dis1)swap(dis1,dis2);
    Lli hrd=(Lli)dis1*(dis2+dis3),con;
    if(dis1==dis3){
      con=(Lli)(cnt+2)*(cnt+1)/2;
    }else if(dis1==dis2){
      con=2*cnt;
    }else if(dis2==dis3){
      con=(Lli)(cnt+1)*cnt/2;
    }else{
      con=cnt;
    }
    if(hrd>res.first)res={hrd,0};
    if(hrd==res.first)res.second+=con;
  }
  auto[hrd,tot]=res;
  printf("%lli %lli\n",hrd,tot);
}

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