Submission #1038375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038375		MMihalev	Hard route (IZhO17_road)	C++14	0 / 100	3 ms	17060 KiB

road

#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<tuple>
#include<set>
#include<map>
#include<random>
#include<chrono>
using namespace std;
const int MAX_N=5e5+5;
int maxd[MAX_N];
int cntd[MAX_N];
int maxd2[MAX_N];
int maxdup[MAX_N];
vector<int>g[MAX_N];
int n;
int cnt;
int ans;
int root;
void dfsdown(int u,int par)
{
    for(int v:g[u])
    {
        if(v==par)continue;
        dfsdown(v,u);
        if(maxd[v]+1>maxd[u])
        {
            maxd2[u]=maxd[u];
            maxd[u]=maxd[v]+1;
            cntd[u]=cntd[v];
        }
        else if(maxd[v]+1==maxd[u])
        {
            maxd2[u]=maxd[u];
            cntd[u]+=cntd[v];
        }
    }
    if(g[u].size()==1)cntd[u]=1;
}
void dfsup(int u,int par)
{
    for(int v:g[u])
    {
        if(v==par)continue;

        int cur=maxd[u];
        if(maxd[v]+1==maxd[u])cur=maxd2[u];
        cur++;

        maxdup[v]=max(maxdup[u],cur);

        dfsup(v,u);
    }
}
int eachtwo(vector<int>& v)
{
    int sum=0;
    int pairs=0;

    for(int x:v)sum+=x;

    for(int x:v)
    {
        sum-=x;
        pairs+=(x*sum);
    }

    return pairs;
}
void dfs(int u,int par)
{
    vector<pair<int,int>>V;//depth,cnt
    vector<pair<int,int>>all;
    vector<pair<int,int>>otherV;

    int up=maxdup[u],curans=0,curcnt=0;

    for(int v:g[u])
    {
        if(v==par)continue;
        dfs(v,u);
        all.push_back({maxd[v]+1,cntd[v]});
    }

    if(g[u].size()==1)return;

    sort(all.begin(),all.end());

    V.push_back(all[0]);
    otherV.push_back({all[0].first,1});

    for(int i=1;i<all.size();i++)
    {
        if(all[i].first==all[i-1].first)
        {
            V.back().second+=all[i].second;
            otherV.back().second++;
        }
        else {V.push_back(all[i]);otherV.push_back({all[i].first,1});}
    }


    if(otherV.back().second>=3)
    {
        int b=V.back().first;
        vector<int>only;

        for(int v:g[u])
        {
            if(v==par)continue;
            if(maxd[v]+1==b)only.push_back(cntd[v]);
        }

        int eachtwob=eachtwo(only);

        curans=2*b*b;
        curcnt=eachtwob;
    }
    else
    {
        if(otherV.back().second==2)
        {
            if(V.size()>=2)
            {
                int b=V.back().first,cb=V.back().second;
                int a=V[V.size()-2].first,ca=V[V.size()-2].second;

                curans=b*(a+b);
                curcnt=ca*cb;
            }
        }
        else
        {
            if(V.size()==2)
            {
                if(otherV[0].second>=2)
                {
                    int b=V[1].first;
                    int a=V[0].first;
                    vector<int>only;

                    for(int v:g[u])
                    {
                        if(v==par)continue;
                        if(maxd[v]+1==a)only.push_back(cntd[v]);
                    }

                    int eachtwoa=eachtwo(only);

                    curans=2*a*b;
                    curcnt=eachtwoa;
                }
            }
            else if(V.size()>2)
            {
                int b=V.back().first,cb=V.back().second;
                int a=V[V.size()-2].first,ca=V[V.size()-2].second;
                int c=V[V.size()-3].first,cc=V[V.size()-3].second;

                curans=b*(a+c);
                curcnt=cc*ca;
            }
        }
    }
    ///without up


    if(otherV.back().second>=2)
    {
        int b=V.back().first;
        vector<int>only;

        for(int v:g[u])
        {
            if(v==par)continue;
            if(maxd[v]+1==b)only.push_back(cntd[v]);
        }

        int eachtwob=eachtwo(only);

        if(2*b*up>curans)
        {
            curans=2*b*up;
            curcnt=eachtwob;
        }
        else if(2*b*up==curans)
        {
            curcnt+=eachtwob;
        }
    }
    else
    {
        if(V.size()>=2)
        {
            int b=V.back().first,cb=V.back().second;
            int a=V[V.size()-2].first,ca=V[V.size()-2].second;

            if((a+b)*up>curans)
            {
                curans=(a+b)*up;
                curcnt=ca*cb;
            }
            else if((a+b)*up==curans)
            {
                curcnt+=ca*cb;
            }
        }
    }
    ///with up


    if(curans>ans)
    {
        ans=curans;
        cnt=curcnt;
    }
    else if(curans==ans)
    {
        cnt+=curcnt;
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    if(n==2)
    {
        cout<<0<<" "<<1<<"\n";
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        if(g[i].size()==1)continue;
        root=i;
        break;
    }
    dfsdown(root,0);
    dfsup(root,0);
    dfs(root,0);
    cout<<ans<<" "<<cnt<<"\n";
    return 0;
}

Compilation message (stderr)

road.cpp: In function 'void dfs(int, int)':
road.cpp:97:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int i=1;i<all.size();i++)
      |                 ~^~~~~~~~~~~
road.cpp:161:38: warning: unused variable 'cb' [-Wunused-variable]
  161 |                 int b=V.back().first,cb=V.back().second;
      |                                      ^~

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