Submission #441172

#	Time	Username	Problem	Language	Result	Execution time	Memory
441172		leaked	Hard route (IZhO17_road)	C++14	100 / 100	1106 ms	163232 KiB

road

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC opimize(-O3)
//#pragma GCC opimize(Ofast)
//#pragma GCC opimize(unroll-loops)
//#pragma GCC target("avx,avx2,popcnt,sse,sse2,sse3,sse4,abm,tune=native")
#define m_p make_pair
#define vec vector
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)
#define f first
#define s second
#define ar array
using namespace std;
using namespace __gnu_pbds;
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
//#define
const int M=1e9+7;
const int N=5e5+4;
const int inf=N;
struct fck{
    int val=-N;
    ll cl=0;
    fck(){
        val=-N;cl=0;
    }
};
void mg(fck &a,fck b){
    if(a.val<b.val) a=b;
    else if(a.val==b.val){
        a.cl+=b.cl;
    }
}
fck dpd[N],dpu[N];
vec<fck>go[N];
vec<int>g[N];
ll ans1=0;
ll ans2=0;
/// a<=b<=c c*(a+b)
void dfs1(int v,int p){
    dpd[v].val=0,dpd[v].cl=1;
    go[v].resize(sz(g[v]));
    for(int i=0;i<sz(g[v]);i++){
        int z=g[v][i];
        if(z==p) continue;
        dfs1(z,v);
        auto lel=dpd[z];
        lel.val++;
        go[v][i]=lel;
        mg(dpd[v],lel);
    }
}
void dfs2(int v,int p,fck from){
    vec<int>sons;
    for(int i=0;i<sz(g[v]);i++){
        int z=g[v][i];
        if(z==p){
            go[v][i]=from;
        }
        else{
            sons.pb(z);
        }
    }
    int n=sz(sons);
    vec<fck>pref(n);
    vec<fck>suf(n);
    {
        fck cr;
        for(int i=0;i<n;i++){
            pref[i]=cr;
            fck lel=dpd[sons[i]];lel.val++;
            mg(cr,lel);
        }
    }
    {
        fck cr;
        for(int i=n-1;i>=0;i--){
            suf[i]=cr;
            fck lel=dpd[sons[i]];lel.val++;
            mg(cr,lel);
        }
    }
    for(int i=0;i<sz(sons);i++){
        int u=sons[i];
        fck lel=from;
        mg(lel,pref[i]);mg(lel,suf[i]);
        lel.val++;
        dfs2(u,v,lel);
    }
}
void ins(vec<ll> &vl,ll x){
    for(int i=2;i>=0;i--){
        if(vl[i]==x) break;
        if(vl[i]<x) swap(vl[i],x);
    }
}
void dfs3(int v,int p){
    for(auto &z : g[v]){
        if(z==p) continue;
        dfs3(z,v);
    }
    if(sz(g[v])<=2) return;
    vec<vec<int>>prek(3,vec<int>());
    vec<ll>value(3,-2);
    for(int i=0;i<sz(g[v]);i++){
        ll x=go[v][i].val;
        ins(value,x);
    }
     for(int i=0;i<sz(g[v]);i++){
        for(int j=0;j<3;j++){
            if(value[j]==go[v][i].val){
                prek[j].pb(go[v][i].cl);
            }
        }
    }
    vec<ll>dp(4,0);
    ll x=-1;
    vec<int>to;
    if(sz(prek[2])==1){
        if(sz(prek[1])>1){
            dp[1]=1;
            x=value[2]*(value[1]+value[1]);
            to=prek[1];
        }
        else if(sz(prek[1])==1 && sz(prek[0])){
            dp[2]=prek[1][0];
            to=prek[0];
            x=value[2]*(value[1]+value[0]);
        }
    }
    else if(sz(prek[2])==2){
        dp[2]=prek[2][0]+prek[2][1];
        to=prek[1];
        if(sz(to))x=1ll*value[2]*(value[2]+value[1]);
    }
    else if(sz(prek[2])>2){
        dp[1]=1;
        to=prek[2];
        if(sz(to))x=1ll*value[2]*(value[2]+value[2]);
    }
    for(auto &z : to){
        dp[3]+=1ll*dp[2]*z;
        dp[2]+=1ll*dp[1]*z;
    }
    if(x>ans1) ans1=x,ans2=dp[3];
    else if(x==ans1) ans2+=dp[3];
//    cerr<<v+1<<' '<<x<<' '<<ans2<<endl;
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//    ifstream cin("road.in");
//    ofstream cout("road.out");
    int n;
    cin>>n;
    for(int i=1;i<n;i++){
        int v,u;
        cin>>v>>u;--v;--u;
        g[v].pb(u);g[u].pb(v);
    }
    int root=-1;
    for(int i=0;i<n;i++){
        if(sz(g[i])>2) root=i;
    }
    if(root==-1){
        cout<<0<<' '<<1;
        ///just line;
        return 0;
    }
    dfs1(root,root);
    fck blya;
    assert(blya.val==-inf);
    dfs2(root,root,blya);
    dfs3(root,root);
    cout<<ans1<<' '<<ans2;
    return 0;
}
/*
7
1 2
1 3
2 4
2 5
3 6
3 7
4
1 2
2 3
2 4

5
1 2
2 3
3 4
4 5

*/

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