제출 #1038642

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1038642		MMihalev	Hard route (IZhO17_road)	C++14	0 / 100	2 ms	12892 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 long long MAX_N=5e5+5;
long long maxd[MAX_N];
long long cntd[MAX_N];
long long maxd2[MAX_N];
long long maxdup[MAX_N];
vector<long long>g[MAX_N];
long long n;
long long cnt;
long long ans;

void dfsdown(long long u,long long par)
{
    for(long long 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(long long u,long long par)
{
    for(long long v:g[u])
    {
        if(v==par)continue;

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

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

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

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

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

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

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

    for(long long 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(long long 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)
    {
        long long b=V.back().first;
        vector<long long>only;

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

        long long eachtwob=eachtwo(only);

        curans=2*b*b;
        curcnt=eachtwob;
    }
    else
    {
        if(otherV.back().second==2)
        {
            if(V.size()>=2)
            {
                long long b=V.back().first,cb=V.back().second;
                long long 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)
                {
                    long long b=V[1].first;
                    long long a=V[0].first;
                    vector<long long>only;

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

                    long long eachtwoa=eachtwo(only);

                    curans=2*a*b;
                    curcnt=eachtwoa;
                }
            }
            else if(V.size()>2)
            {
                long long b=V.back().first,cb=V.back().second;
                long long a=V[V.size()-2].first,ca=V[V.size()-2].second;
                long long 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)
    {
        long long b=V.back().first;
        vector<long long>only;

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

        long long 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)
        {
            long long b=V.back().first,cb=V.back().second;
            long long 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;
    }
}
pair<int,int>diam(int u,int par)
{
    pair<int,int>res={u,0};
    for(int v:g[u])
    {
        if(v==par)continue;
        if(diam(v,u).second+1>res.second)
        {
            res=diam(v,u);
            res.second++;
        }
    }
    return res;
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n;
    for(long long i=1;i<n;i++)
    {
        long long u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    int distant=diam(1,0).first;
    int root=diam(distant,0).first;

    dfsdown(root,0);
    dfsup(root,0);
    dfs(root,0);

    if(ans==0)cnt=1;
    cout<<ans<<" "<<cnt<<"\n";

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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