oj.uz

답안 #827895

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
827895 2023-08-16T21:50:40 Z EthanKim8683 Hard route (IZhO17_road) C++17
0 / 100
 7 ms 12076 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 5 ms 11988 KB Output is correct
3 Correct 7 ms 12044 KB Output is correct
4 Correct 5 ms 12048 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 12056 KB Output is correct
7 Incorrect 7 ms 12076 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 5 ms 11988 KB Output is correct
3 Correct 7 ms 12044 KB Output is correct
4 Correct 5 ms 12048 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 12056 KB Output is correct
7 Incorrect 7 ms 12076 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 5 ms 11988 KB Output is correct
3 Correct 7 ms 12044 KB Output is correct
4 Correct 5 ms 12048 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 12056 KB Output is correct
7 Incorrect 7 ms 12076 KB Output isn't correct
8 Halted 0 ms 0 KB -