Submission #169953

#	Time	Username	Problem	Language	Result	Execution time	Memory
169953		stefdasca	Hard route (IZhO17_road)	C++14	0 / 100	15 ms	12156 KiB

road

#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9

using namespace std;

typedef long long ll;

int n;
ll mx = 0;
ll ct = 0;
vector<int> v[500002];
int dist[500002], mxn[500002];
void dfs(int dad, int nod)
{
    for(int i = 0; i < v[nod].size(); ++i)
    {
        int vecin = v[nod][i];
        if(vecin == dad)
            continue;
        dfs(nod, vecin);
        dist[nod] = max(dist[nod], dist[vecin] + 1);
    }
}
void dfs2(int dad, int nod, int mx)
{
    mxn[nod] = mx;
    int mxx = 0, mxx2 = 0;
    for(int i = 0; i < v[nod].size(); ++i)
    {
        int vecin = v[nod][i];
        if(vecin == dad)
            continue;
        if(dist[vecin] + 1 > mxx)
            mxx2 = mxx, mxx = dist[vecin] + 1;
        else
            if(dist[vecin] + 1 > mxx2)
                mxx2 = dist[vecin] + 1;
    }
    for(int i = 0; i < v[nod].size(); ++i)
    {
        int vecin = v[nod][i];
        if(vecin == dad)
            continue;
        if(dist[vecin] + 1 == mxx)
        {
            if(mx != 0)
                dfs2(nod, vecin, max(mx + 1, mxx2 + 1));
            else
                dfs2(nod, vecin, mxx2 + 1);
        }
        else
        {
            if(mx != 0)
                dfs2(nod, vecin, max(mx + 1, mxx + 1));
            else
                dfs2(nod, vecin, mxx + 1);
        }
    }
}
pair<int, int> dp[500002];
void dfsdp(int dad, int nod)
{
    if(v[nod].size() == 1)
    {
        dp[nod] = {0, 0};
        return;
    }
    for(int i = 0; i < v[nod].size(); ++i)
    {
        int vecin = v[nod][i];
        if(vecin == dad)
            continue;
        dfsdp(nod, vecin);
    }
    int mxothr = 0;
    int wh = 0;
    int cot = 0;
    for(int i = 0; i < v[nod].size(); ++i)
    {
        int vecin = v[nod][i];
        if(vecin == dad)
            continue;
        if(dp[vecin].fi + 1 > dp[nod].fi)
            wh = i, dp[nod] = dp[vecin], dp[nod].fi++, cot = 1;
        else
            if(dp[vecin].fi + 1 == dp[nod].fi && dp[vecin].se > dp[nod].se)
                wh = i, dp[nod] = dp[vecin], dp[nod].fi++, ++cot;
    }
    if(mxn[nod] >= dist[nod])
    {
        if(cot >= 2)
        {
            if(2LL * dp[nod].fi * mxn[nod] > mx)
                mx = 2 * dp[nod].fi, ct = 1LL * cot * (cot - 1) / 2;
            else
                if(2LL * mxn[nod] * dp[nod].fi == mx)
                    ct += 1LL * cot * (cot - 1) / 2;
        }
        else
        {
            for(int i = 0; i < v[nod].size(); ++i)
            {
                int vecin = v[nod][i];
                if(vecin == dad)
                    continue;
                if(i != wh)
                {
                    if(1LL * mxn[nod] * (dp[nod].fi + dp[vecin].fi + 1) > mx)
                        mx = 1LL * mxn[nod] * (dp[nod].fi + dp[vecin].fi + 1), ct = 1;
                    else
                        if(1LL * mxn[nod] * (dp[nod].fi + dp[vecin].fi + 1) == mx)
                            ++ct;
                }
            }
        }
    }
    else
    {
        vector<pair<int, int> >vx;
        for(int i = 0; i < v[nod].size(); ++i)
        {
            int vecin = v[nod][i];
            if(vecin == dad)
                continue;
            vx.pb({dp[vecin].fi + 1, dp[vecin].se});
          //  cout << dp[vecin].fi + 1 << " " << dp[vecin].se << '\n';
        }
        sort(vx.begin(), vx.end());
        for(int j = vx.size() - 1; j >= 0; )
        {
            bool rau = 0;
            if(j != vx.size() - 1)
                rau = 1;
            int i = j;
            while(i >= 0 && vx[j] == vx[i])
                --i;
            ll countt = j - i;
          //  cout << vx[j].fi << " " << vx[j].se << " " << countt << '\n';
            if(countt >= 2)
            {
                if(j == vx.size() - 1)
                {
                    ll di = 2LL * vx[j].fi;
                    if(countt == 2)
                        if(i >= 0)
                            di = di * max(mxn[nod], max(vx[i].fi, vx[j].se));
                        else
                            di = di * max(mxn[nod], vx[j].se);
                    else
                        di = di * vx[j].fi;
                    if(di > mx)
                        mx = di, ct = 1LL * countt * (countt - 1) / 2;
                    else
                        if(di == mx)
                            ct += 1LL * countt * (countt - 1) / 2;
                }
                else
                {
                    ll di = 2LL * vx[j].fi * max(mxn[nod], vx.back().fi);
                    if(di > mx)
                        mx = di, ct = 1LL * countt * (countt - 1) / 2;
                    else
                        if(di == mx)
                            ct += 1LL * countt * (countt - 1) / 2;
                }
            }
            else
            {
                for(int pp = j - 1; pp >= 0; --pp)
                {
                    ll dist = vx[j].fi + vx[pp].fi;
                    if(j != vx.size() - 1)
                        dist = dist * vx.back().fi;
                    else
                        if(pp == j-1)
                        {
                            if(pp == 0)
                                dist = dist * max(max(vx[j].se, vx[pp].se), mxn[nod]);
                            else
                                dist = dist * max(max(vx[j].se, vx[pp].se), max(mxn[nod], vx[j - 1].fi));
                        }
                }
            }
            j = i;
            if(rau)
                break;
        }
    }
    for(int i = 0; i < v[nod].size(); ++i)
    {
        int vecin = v[nod][i];
        if(vecin == dad)
            continue;
        if(i != wh)
            dp[nod].se = max(dp[nod].se, dp[vecin].fi + 1);
        else
            dp[nod].se = max(dp[nod].se, dp[vecin].se);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    int nL = 0;
    for(int i = 1; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;
        v[a].pb(b);
        v[b].pb(a);
    }
    for(int i = 1; i <= n; ++i)
        if(v[i].size() == 1)
            ++nL;
    if(nL == 2)
    {
        cout << 0 << " " << 1;
        return 0;
    }
    int root = 0;
    for(int i = 1; i <= n; ++i)
        if(v[i].size() != 1)
        {
            root = i;
            break;
        }
    dfs(0, root);
    dfs2(0, root, 0);
    dfsdp(0, root);
    cout << mx << " " << ct << '\n';
    return 0;
}

Compilation message (stderr)

road.cpp: In function 'void dfs(int, int)':
road.cpp:23:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); ++i)
                    ~~^~~~~~~~~~~~~~~
road.cpp: In function 'void dfs2(int, int, int)':
road.cpp:36:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); ++i)
                    ~~^~~~~~~~~~~~~~~
road.cpp:47:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); ++i)
                    ~~^~~~~~~~~~~~~~~
road.cpp: In function 'void dfsdp(int, int)':
road.cpp:76:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); ++i)
                    ~~^~~~~~~~~~~~~~~
road.cpp:86:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); ++i)
                    ~~^~~~~~~~~~~~~~~
road.cpp:109:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < v[nod].size(); ++i)
                            ~~^~~~~~~~~~~~~~~
road.cpp:128:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < v[nod].size(); ++i)
                        ~~^~~~~~~~~~~~~~~
road.cpp:140:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(j != vx.size() - 1)
                ~~^~~~~~~~~~~~~~~~
road.cpp:149:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(j == vx.size() - 1)
                    ~~^~~~~~~~~~~~~~~~
road.cpp:180:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if(j != vx.size() - 1)
                        ~~^~~~~~~~~~~~~~~~
road.cpp:197:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); ++i)
                    ~~^~~~~~~~~~~~~~~
road.cpp:83:9: warning: unused variable 'mxothr' [-Wunused-variable]
     int mxothr = 0;
         ^~~~~~

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