Submission #169961

#	Time	Username	Problem	Language	Result	Execution time	Memory
169961		stefdasca	Hard route (IZhO17_road)	C++14	19 / 100	2021 ms	12536 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;
vector<int> v[500002];
int dist[500002];
ll mx, ct;
ll tmx, tmx2;
ll prv[500002];
ll viz[500002];
void dfs(int dad, int nod, int lf1, int lf2)
{
    prv[nod] = dad;
    if(nod == lf1)
        dist[nod] = 0;
    else
    {
        dist[nod] = dist[dad] + 1;
        if(nod == lf2)
            tmx = dist[nod];
    }
    for(int i = 0; i < v[nod].size(); ++i)
    {
        int vecin = v[nod][i];
        if(vecin == dad)
            continue;
        dfs(nod, vecin, lf1, lf2);
    }
}
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;
    }
    for(int i = 1; i <= n; ++i)
        if(v[i].size() == 1)
            for(int j = i+1; j <= n; ++j)
            {
                if(v[j].size() != 1)
                    continue;
                tmx2 = 0;
                tmx = 0;
                dfs(0, i, i, j);
                deque<int> d;
                int ndd = j;
                while(ndd)
                {
                    viz[ndd] = 1;
                    d.pb(ndd);
                    ndd = prv[ndd];
                }
                while(!d.empty())
                {
                    int nod = d[0];
                    d.pop_front();
                    tmx2 = max(tmx2, viz[nod] - 1);
                    for(int j = 0; j < v[nod].size(); ++j)
                    {
                        int vecin = v[nod][j];
                        if(viz[vecin])
                            continue;
                        viz[vecin] = viz[nod] + 1;
                        d.pb(vecin);
                    }
                }
                for(int xxx = 1; xxx <= n; ++xxx)
                    prv[xxx] = viz[xxx] = 0;
                if(tmx * tmx2 == mx)
                    ++ct;
                else
                    if(tmx * tmx2 > mx)
                        mx = tmx * tmx2, ct = 1;
            }
    cout << mx << " " << ct << '\n';
    return 0;
}

Compilation message (stderr)

road.cpp: In function 'void dfs(int, int, int, int)':
road.cpp:34:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); ++i)
                    ~~^~~~~~~~~~~~~~~
road.cpp: In function 'int main()':
road.cpp:85:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for(int j = 0; j < v[nod].size(); ++j)
                                    ~~^~~~~~~~~~~~~~~

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