Submission #1184363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184363		FaresSTH	Hard route (IZhO17_road)	C++20	100 / 100	517 ms	77324 KiB

road

#include"bits/stdc++.h"
using namespace std;
using ll=long long;
#define S second
#define F first
const int mxn=6e5;
ll par[mxn],d[mxn],mx,x,Sigma,y,Alpha,IDontLikeSpecialCases,MaximumOfTheGalaxy[mxn],WHEREISOMNIMANWHEREISHE,AREYOUSURE,ANNOYINGFERMAT;
bool DoubleFreakyNoCap[mxn],tm8x[mxn],tm8y[mxn];
vector<ll>adj[mxn],pth,cur;
bool Freaky[mxn],f=1;
void dia(int i,int p,int l){
    for(int j:adj[i]){
        if(j==p)continue;
        dia(j,i,l+1);
    }
    if(l>mx){
        if(f)x=i,Sigma=1;
        else y=i,Alpha=1;
        mx=l;
    }
    else if(l==mx){
        if(f)Sigma++;
        else Alpha++;
    }
}
void dfs(int i,int p){
    cur.push_back(i);
    for(int j:adj[i]){
        if(j==p)continue;
        dfs(j,i);
    }
    if(i==y)pth=cur;
    cur.pop_back();
}
void FreaknessLevel(int i,int p,int l,bool t){
    for(int j:adj[i]){
        if(j==p)continue;
        FreaknessLevel(j,i,l+1,t);
    }
    if(l==mx){
        if(Freaky[i])DoubleFreakyNoCap[i]=1,ANNOYINGFERMAT++;
        else Freaky[i]=1;
    }
    if(!t&&Freaky[i]&&!DoubleFreakyNoCap[i]){
        if(l==mx)WHEREISOMNIMANWHEREISHE++,tm8x[i]=1;
        else AREYOUSURE++,tm8y[i]=1;
    }
}
void calc(int i,int p,int pre,int nxt,ll l,int ExtremeParent){
    par[i]=ExtremeParent;
    for(int j:adj[i]){
        if(j==p||j==pre||j==nxt)continue;
        calc(j,i,0,0,l+1,ExtremeParent);
    }
    IDontLikeSpecialCases=max(IDontLikeSpecialCases,l);
    MaximumOfTheGalaxy[i]=l;
}
ll IMSOLONELY(ll a,ll b,ll c){
    return a*b+c*(c-1)/2+c*(a+b);
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin>>n;
    f=1;
    for(int i=1,a,b;i<n;i++){
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        if(adj[a].size()>2||adj[b].size()>2)f=0;
    }
    if(f)return cout<<"0 1",0;
    f=1,mx=0;dia(1,0,0);
    f=0,mx=0;dia(x,0,0);
    f=1,mx=0;dia(y,0,0);
    FreaknessLevel(x,0,0,1);
    FreaknessLevel(y,0,0,0);
    dfs(x,0);
    for(int i=0;i<=mx;i++){
        calc(pth[i],0,(i?pth[i-1]:0),(i<mx?pth[i+1]:0),0,pth[i]);
        d[pth[i]]=i;
    }
    pair<ll,ll>res={mx*IDontLikeSpecialCases,0ll};
    Sigma++,Alpha++;
    for(int i=1;i<=n;i++){
        if((int)adj[i].size()>1||i==x||i==y)continue;
        ll a=d[par[i]]*(MaximumOfTheGalaxy[i]+mx-d[par[i]]);
        ll b=(mx-d[par[i]])*(MaximumOfTheGalaxy[i]+d[par[i]]);
        res.F=max({res.F,a,b});
    }
    ll A=0,B=0,C=0;
    bool fr[2]={1,1};
    for(int i=1;i<=n;i++){
        if((int)adj[i].size()>1||i==x||i==y)continue;
        ll a=d[par[i]]*(MaximumOfTheGalaxy[i]+mx-d[par[i]]);   //y
        ll b=(mx-d[par[i]])*(MaximumOfTheGalaxy[i]+d[par[i]]); //x
        if(max(a,b)!=res.F)continue;
        if(DoubleFreakyNoCap[i]){
            A=(ANNOYINGFERMAT+1)*(ANNOYINGFERMAT+2)/2ll;
            B=0,C=0;
            break;
        }
        else if(Freaky[i]){
            if(tm8x[i]&&fr[0]){
                B+=WHEREISOMNIMANWHEREISHE-1;
                C+=ANNOYINGFERMAT;
                fr[0]=0;
            }
            else if(tm8y[i]&&fr[1]){
                B+=AREYOUSURE-1;
                C+=ANNOYINGFERMAT;
                fr[1]=0;
            }
            B+=(a>b?AREYOUSURE-1:WHEREISOMNIMANWHEREISHE-1);
            C+=ANNOYINGFERMAT;
        }
        else{
            if(a==b)C+=WHEREISOMNIMANWHEREISHE+AREYOUSURE+ANNOYINGFERMAT;
            else C+=(a>b?AREYOUSURE:WHEREISOMNIMANWHEREISHE)+ANNOYINGFERMAT;
        } 
    }
    // cout<<"f";
    // if(res.F==75180)cout<<A<<' '<<B<<' '<<C<<'\n';
    cout<<res.F<<' '<<A+B/2ll/(fr[0]^fr[1]?2ll:1ll)+C;
    // cout<<'\n'<<ANNOYINGFERMAT<<' '<<WHEREISOMNIMANWHEREISHE<<' '<<AREYOUSURE;
    // cout<<'\n'<<x<<' '<<y;
    // cout<<'\n'<<IMSOLONELY(WHEREISOMNIMANWHEREISHE,AREYOUSURE,ANNOYINGFERMAT-1);
}

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