Submission #868545

#	Time	Username	Problem	Language	Result	Execution time	Memory
868545		LeVanThuc	Hard route (IZhO17_road)	C++17	100 / 100	624 ms	139888 KiB

road

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define p(x,y) pair<ll,ll>(x,y)
#define BIT(i,x) ((x>>i)&1)
#define MASK(x) (1<<x)
#define ld long double
#define __builtin_popcount __builtin_popcountll
#define pll pair<ll,ll>
template<class T1,class T2>
bool maximize(T1 &x,const T2 &y)
{
    if(x<y)
    {
        x=y;
        return 1;
    }
    return 0;
}
template<class T1,class T2>
bool minimize(T1 &x,const T2 &y)
{
    if(x>y)
    {
        x=y;
        return 1;
    }
    return 0;
}
void online()
{
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
#ifdef thuc
    freopen("input.INP","r",stdin);
    freopen("output.OUT","w",stdout);
#else

#endif
}
const ll N=5e5+10,M=1e9+7;
ll par[N],in[N],cnt[N],n,ans,res;
vector<ll> gr[N];
void dfs(ll u)
{
    cnt[u]=1;
    in[u]=1;
    for(auto v:gr[u])
    {
        if(v==par[u]) continue;
        par[v]=u;
        dfs(v);
        if(maximize(in[u],in[v]+1)) cnt[u]=0;
        if(in[u]==in[v]+1)
        {
            cnt[u]+=cnt[v];
        }
    }
}
void dp(ll u,ll out,ll outc)
{
    vector<pll> vt;
    if(u!=1)
    vt.emplace_back(out,outc);
    for(auto v:gr[u])
    {
        if(v==par[u]) continue;
        vt.emplace_back(in[v],cnt[v]);
    }
    sort(vt.begin(),vt.end(),greater<pll>());
    if(vt.size()>=3&&(vt[0].fi*(vt[1].fi+vt[2].fi))>=res)
    {
        ll curres=(vt[0].fi*(vt[1].fi+vt[2].fi)),curcnt=0;
        ll ba=0;
        for(auto v:vt)
        {
            if(v.fi==vt[2].fi) ba+=v.se;
        }
        if(vt[1].fi==vt[2].fi)
        {
            ll cnt=0;
            for(auto [x,num]:vt)
            {
                if(x==vt[1].fi)
                {
                    curcnt+=cnt*num;
                    cnt+=num;
                }
            }
        }
        else if(vt[0].fi==vt[1].fi)
        {
            curcnt=(vt[0].se+vt[1].se)*ba;
        }
        else
        {
            curcnt=vt[1].se*ba;
        }
        if(maximize(res,curres)) ans=0;
        ans+=curcnt;
    }
    ll mx1=vt[0].fi,mx1c=0,mx2=0,mx2c=1;
    if(vt.size()>=2) mx2=vt[1].fi,mx2c=0;
    for(auto [v,num]:vt)
    {
        if(v==mx1) mx1c+=num;
        if(v==mx2) mx2c+=num;
    }
    for(auto v:gr[u])
    {
        if(v==par[u]) continue;
        if(in[v]==mx1)
        {
            if(cnt[v]==mx1c) dp(v,mx2+1,mx2c);
            else dp(v,mx1+1,mx1c-cnt[v]);
        }
        else dp(v,mx1+1,mx1c);
    }
}
int main()
{
    online();
    cin>>n;
    ans=1;
    for(int i=1; i<n; i++)
    {
        ll u,v;
        cin>>u>>v;
        gr[u].push_back(v);
        gr[v].push_back(u);
    }
    ll flag=1,cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(gr[i].size()>2) flag=0;
        if(gr[i].size()==1) cnt++;
    }
//    if(flag&&cnt==2)
//    {
//        cout<<"0 1";
//        return 0;
//    }
    dfs(1);
    dp(1,0,1);
    cout<<res<<' '<<ans<<'\n';
}

Compilation message (stderr)

road.cpp: In function 'int main()':
road.cpp:134:8: warning: variable 'flag' set but not used [-Wunused-but-set-variable]
  134 |     ll flag=1,cnt=0;
      |        ^~~~

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