Submission #1133486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133486		sofija6	Hard route (IZhO17_road)	C++20	100 / 100	623 ms	125432 KiB

road

#include <bits/stdc++.h>
#define ll long long
#define MAXN 500010
using namespace std;
ll maxx[MAXN],cnt[MAXN];
vector<ll> G[MAXN];
void DFS_Dist(ll i,ll p)
{
    maxx[i]=0;
    cnt[i]=1;
    for (ll next : G[i])
    {
        if (next!=p)
        {
            DFS_Dist(next,i);
            if (maxx[next]+1==maxx[i])
                cnt[i]+=cnt[next];
            else if (maxx[next]+1>maxx[i])
            {
                maxx[i]=maxx[next]+1;
                cnt[i]=cnt[next];
            }
        }
    }
}
vector<pair<ll,ll> > dist[MAXN];
ll ans,cntans=1;
void DFS_Solve(ll i,ll p)
{
    if (p)
    {
        if (dist[p][0].first==maxx[i]+1 && dist[p][0].second==cnt[i])
        {
            if (dist[p].size()>1)
                dist[i].push_back({dist[p][1].first+1,dist[p][1].second});
            else
                dist[i].push_back({1,1});
        }
        else
            dist[i].push_back({dist[p][0].first+1,dist[p][0].second});
    }
    for (ll next : G[i])
    {
        if (next!=p)
            dist[i].push_back({maxx[next]+1,cnt[next]});
    }
    sort(dist[i].begin(),dist[i].end(),greater<pair<ll,ll> >());
    ll maxxh=0,cur=0;
    if (dist[i].size()>2)
    {
        ll maxx1=dist[i][0].first,maxx2=dist[i][1].first,maxx3=dist[i][2].first,same=0;
        maxxh=maxx1*(maxx2+maxx3);
        for (auto i : dist[i])
        {
            if (i.first==maxx3)
                same+=i.second;
        }
        if (maxx1!=maxx2 && maxx2!=maxx3)
            cur+=dist[i][1].second*same;
        else if (maxx1==maxx2 && maxx2!=maxx3)
            cur+=(dist[i][0].second+dist[i][1].second)*same;
        else
        {
            for (auto i : dist[i])
            {
                if (i.first==maxx3)
                    cur+=i.second*(same-i.second);
            }
            cur/=2;
        }
        if (maxxh>ans && cur)
        {
            ans=maxxh;
            cntans=cur;
        }
        else if (maxxh==ans)
            cntans+=cur;
    }
    for (ll next : G[i])
    {
        if (next!=p)
            DFS_Solve(next,i);
    }
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,u,v;
    cin >> n;
    for (ll i=1;i<n;i++)
    {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    DFS_Dist(1,0);
    DFS_Solve(1,0);
    cout << ans << " " << cntans << "\n";
    return 0;
}

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