Submission #1182925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182925		FaresSTH	Hard route (IZhO17_road)	C++20	19 / 100	2095 ms	15424 KiB

road

#include"bits/stdc++.h"
using namespace std;
using ll=long long;
#define S second
#define F first
const int mxn=6e5;
int p[mxn][30],d[mxn],mx,x;
vector<int>adj[mxn];
void dfs(int i){
    d[i]=d[p[i][0]]+1;
    for(int j:adj[i]){
        if(j==p[i][0])continue;
        p[j][0]=i;
        dfs(j);
    }
}
void diamiter(int i,int p,int l){
    for(int j:adj[i]){
        if(j==p)continue;
        diamiter(j,i,l+1);
    }
    if(l>mx){
        mx=l;
        x=i;
    }
}
pair<int,int>dis(int a,int b){
    int res=0;
    if(d[a]>d[b]){
        for(int i=25;i>=0;i--){
            if(d[p[a][i]]>d[b])a=p[a][i],res+=(1<<i);
        }
        a=p[a][0];
        res++;
    }
    if(d[b]>d[a]){
        for(int i=25;i>=0;i--){
            if(d[p[b][i]]>d[a])b=p[b][i],res+=(1<<i);
        }
        b=p[b][0];
        res++;
    }
    if(a==b)return {res,a};
    for(int i=25;i>=0;i--){
        if(p[a][i]!=p[b][i])a=p[a][i],b=p[b][i],res+=(1ll<<(i+1));
    }
    res++,res++;
    return {res,p[a][0]};
}
int pwease(int a,int b){
    if(a==b)return 0;
    int res=1;
    for(int i=25;i>=0;i--){
        if(d[p[a][i]]>d[b])a=p[a][i],res+=(1<<i);
    }
    return res;
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin>>n;
    for(int i=1,a,b;i<n;i++){
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    bool f=1;
    int st;
    for(int i=1;i<=n;i++){
        if((int)adj[i].size()>2)f=0,st=i;
    }
    if(f)return cout<<"0 1",0;
    dfs(st);

    for(int j=1;j<=25;j++){
        for(int i=1;i<=n;i++){
            p[i][j]=p[p[i][j-1]][j-1];
        }
    }
    diamiter(1,0,0);
    vector<int>sigma_7aly={x};
    diamiter(x,0,0);
    sigma_7aly.push_back(x);
    pair<ll,ll>res={0,0};
    int cournt=-1;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if((int)adj[i].size()>1||(int)adj[j].size()>1)continue;
            ll cur=0;
            bool f=1;
            for(int k:sigma_7aly){
                if(k==i||k==j)continue;
                f=0;
                int a=pwease(i,dis(i,j).S),b=pwease(i,dis(i,k).S);
                int mn=ll(dis(i,k).F-min(a,b));
                a=pwease(j,dis(i,j).S),b=pwease(j,dis(j,k).S);
                mn=min(mn,dis(j,k).F-min(a,b));
                cur=max(cur,ll(mn));
            }
            if(f){
                if(cournt!=-1)cur=cournt;
                else{
                    for(int k=1;k<=n;k++){
                        if((int)adj[k].size()>1||k==i||k==j)continue;
                        int a=pwease(i,dis(i,j).S),b=pwease(i,dis(i,k).S);
                        int mn=ll(dis(i,k).F-min(a,b));
                        a=pwease(j,dis(i,j).S),b=pwease(j,dis(j,k).S);
                        mn=min(mn,dis(j,k).F-min(a,b));
                        cur=max(cur,ll(mn));
                    }
                    cournt=cur;
                }
            }
            cur*=dis(i,j).F;
            if(cur>res.F)res={cur,1};
            else if(cur==res.F)res.S++;
        }
    }
    cout<<res.F<<' '<<res.S;
}

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