Submission #440812

#	Time	Username	Problem	Language	Result	Execution time	Memory
440812		leaked	Hard route (IZhO17_road)	C++14	0 / 100	51 ms	78600 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=1e6+1;
const ll inf=1e18;
int mult(int a,int b){
    return 1ll*a*b%M;
}
void add(int &a,int b){
    a+=b;
    if(a>=M) a-=M;
    else if(a<0) a+=M;
}
int sum(int a,int b){
    int x=a+b;
    if(x>=M) x-=M;
    else if(x<0) x+=M;
    return x;
}
struct fck{
    ll val=-1e18,cl=0;
    fck(){
        val=-1e18;cl=0;
    }
};
void mg(fck &a,fck &b){
    if(a.val<b.val) swap(a,b);
    else if(a.val==b.val){
        a.cl+=b.cl;
        b.val=-1,b.cl=-1;
    }
    a.cl%=M;
}
fck dpd[N],dpu[N];
vec<fck>go[N];
vec<int>g[N];
ll ans1=0;
int 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;
            mg(cr,dpd[sons[i]]);
        }
    }
    {
        fck cr;
        for(int i=n-1;i>=0;i--){
            suf[i]=cr;
            mg(cr,dpd[sons[i]]);
        }
    }
    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 dfs3(int v,int p){
    for(auto &z : g[v]){
        if(z==p) continue;
        dfs3(z,v);
    }
    vec<vec<int>>prek(3,vec<int>());
    vec<ll>value(3,-inf);
    for(int i=0;i<sz(g[v]);i++){
        ll x=go[v][i].val;
        int id=lower_bound(all(value),x)-value.begin();
        if(binary_search(all(value),x)){
            prek[id].pb(go[v][i].cl);
            continue;
        }
        if(value[0]>x) continue;
        prek.insert(prek.begin()+id,vec<int>());value.insert(value.begin()+id,x);
        prek[id].pb(go[v][i].cl);
        value.erase(value.begin(),value.begin()+1);prek.erase(prek.begin(),prek.begin()+1);
    }
    vec<int>dp(4,0);
    ll x=-1;
    vec<int>to;
    if(sz(prek[2])==1){
        int w=prek[2][0];
        if(sz(prek[1])>1){
            dp[1]=w;
            x=value[2]*(value[1]+value[1]);
            to=prek[1];
        }
        else if(sz(prek[1])==1 && sz(prek[0])){
            dp[2]=mult(prek[1][0],prek[2][0]);
            x=value[2]*(value[1]+value[0]);
            to=prek[2];
        }
    }
    else if(sz(prek[2])==2){
        dp[2]=mult(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){
        add(dp[3],mult(dp[2],z));
        add(dp[2],mult(dp[1],z));
        add(dp[1],mult(dp[0],z));
    }
    if(x>ans1) ans1=x,ans2=dp[3];
    else if(x==ans1) add(ans2,dp[3]);
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    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: 0 / 19
• Subtask 2: 0 / 33
• Subtask 3: 0 / 48