제출 #1038732

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1038732		MMihalev	Hard route (IZhO17_road)	C++14	0 / 100	2 ms	600 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=2e2+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 depth[MAX_N];
int distant;
int root;
int diamsize;

void dfsdown(int u,int par)
{
    for(int v:g[u])
    {
        if(v==par)continue;
        depth[v]=depth[u]+1;
        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;
}
int dp[MAX_N];
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];

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

        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[V.size()-2].second>=2)
                {
                    int b=V[V.size()-1].first;
                    int a=V[V.size()-2].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;
    }
}
pair<int,int>diam(int u,int par)
{
    pair<int,int>res={u,0};
    for(int v:g[u])
    {
        if(v==par)continue;
        auto cur=diam(v,u);
        if(cur.second+1>res.second)
        {
            res.first=cur.first;
            res.second=cur.second+1;
        }
    }
    return res;
}
void solvefor()
{
    for(int i=1;i<=n;i++)
    {
        if(g[i].size()!=1 or i==root)continue;
        int curhardness=depth[i]*dp[i];
        if(curhardness>ans)
        {
            ans=curhardness;
            cnt=1;
        }
        else if(curhardness==ans)cnt++;
    }
}


/// special case :
int p[MAX_N];
int T;
int in[MAX_N];
int out[MAX_N];
void init(int u,int par)
{
    in[u]=++T;
    for(int v:g[u])
    {
        if(v==par)continue;
        init(v,u);
    }
    out[u]=T;
}
void check(int u,int par)
{
    int mi=1e9;
    int cmin;
    for(int v:g[u])
    {
        if(v==par)continue;
        check(v,u);
        if(maxd[v]+1<mi)
        {
            mi=maxd[v]+1;
            cmin=cntd[v];
        }
    }
    if(g[u].size()==3 && in[u]<=in[distant] && in[distant]<=out[u] && mi==depth[u] && depth[u]*2<diamsize)
    {
        cnt+=cmin*(p[out[u]]-p[in[u]]);//-1
    }
}
void solvespecialcase()
{
    if(ans>=1 && ans%diamsize==0)
    {
        int x=ans/diamsize;
        init(root,0);
        for(int i=1;i<=n;i++)
        {
            p[in[i]]=(depth[i]==diamsize && dp[i]==x);
        }
        for(int i=1;i<=n;i++)p[i]+=p[i-1];
        check(root,0);
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("road.in","r",stdin);
    freopen("road.out","w",stdout);

    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);
    }

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

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

    solvefor();
    solvespecialcase();

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

    return 0;
}

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

road.cpp: In function 'void dfs(int, int)':
road.cpp:103: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]
  103 |     for(int i=1;i<all.size();i++)
      |                 ~^~~~~~~~~~~
road.cpp:166:42: warning: unused variable 'cb' [-Wunused-variable]
  166 |                     int b=V.back().first,cb=V.back().second;
      |                                          ^~
road.cpp: In function 'int main()':
road.cpp:317:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  317 |     freopen("road.in","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
road.cpp:318:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  318 |     freopen("road.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
road.cpp: In function 'void check(int, int)':
road.cpp:295:18: warning: 'cmin' may be used uninitialized in this function [-Wmaybe-uninitialized]
  295 |         cnt+=cmin*(p[out[u]]-p[in[u]]);//-1
      |              ~~~~^~~~~~~~~~~~~~~~~~~~~

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