Submission #172283

#	Time	Username	Problem	Language	Result	Execution time	Memory
172283		emil_physmath	Hard route (IZhO17_road)	C++17	52 / 100	868 ms	111396 KiB

road

// #define DEBUG
// #define STRESS_TESTING
#include <algorithm>
#include <vector>
#include <iostream>
#include <cstring>
#include <map>
using namespace std;
typedef long long llong;
const int maxN = 500005;

vector<int> nei[maxN];
pair<int, int> ray[maxN][3];
map<llong, llong> ans;
vector<pair<int, int>> dists[maxN];

namespace AC
{
    int n;
    pair<int, int> maxdist[maxN];
    bool used[maxN];

    void MaxDist(int u);
    pair<int, int> DFS(int u, int dep, int dist);
    void Solve(int n_)
    {
        n = n_;
        pair<int, int> ans(0, 0);
        for (int u=1; u<=n; u++)
            if (nei[u].size()==1)
            {
                memset(used+1, 0, n*sizeof(bool));
                MaxDist(u);
                memset(used+1, 0, n*sizeof(bool));
                pair<int, int> curAns=DFS(u, 0, 0);
                if (curAns.first>ans.first) ans=curAns;
                else if (curAns.first==ans.first) ans.second+=curAns.second;
            }
        cout<<ans.first<<' '<<ans.second/2<<'\n';
    }

    pair<int, int> DFS(int u, int dep, int dist)
    {
        used[u]=true;
        if (nei[u].size()==1 && used[nei[u][0]])
            return make_pair(dep*dist, 1);
        pair<int, int> ans(0, 0);
        for (int i=0; i<nei[u].size(); i++)
        {
            int to=nei[u][i];
            if (!used[to])
            {
                pair<int, int> curAns;
                if (maxdist[u].first==maxdist[to].first+1)
                    curAns=DFS(to, dep+1, max(dist, maxdist[u].second));
                else
                    curAns=DFS(to, dep+1, max(dist, maxdist[u].first));

                if (curAns.first>ans.first) ans=curAns;
                else if (curAns.first==ans.first) ans.second+=curAns.second;
            }
        }
        return ans;
    }

    void MaxDist(int u)
    {
        used[u]=true;
        maxdist[u]=make_pair(0, 0);
        if (nei[u].size()==1 && used[nei[u][0]]) return;
        for (int i=0; i<nei[u].size(); i++)
        {
            int to=nei[u][i];
            if (!used[to])
            {
                MaxDist(to);
                int temp=maxdist[to].first+1;
                if (temp>maxdist[u].first)
                {
                    swap(maxdist[u].first, maxdist[u].second);
                    maxdist[u].first=temp;
                }
                else if (temp>maxdist[u].second)
                    maxdist[u].second=temp;
            }
        }
    }
};
inline ostream& operator<<(ostream& ostr, const pair<int, int>& a)
{
    return ostr << "{" << a.first << ", " << a.second << "}";
}
void Maximize(pair<int, int>* a, pair<int, int> x)
{
    if (a[0].first == x.first)
        a[0].second += x.second;
    else if (a[1].first == x.first)
        a[1].second += x.second;
    else if (a[2].first == x.first)
        a[2].second += x.second;
    else if (x.first > a[2].first)
    {
        a[2] = x;
        sort(a, a + 3, greater<pair<int, int>>());
    }
}
void SetDown(int v, int par)
{
    fill(ray[v], ray[v] + 3, make_pair(0, 0));
    ray[v][0] = {0, 1};
    for (int to: nei[v])
        if (to != par)
        {
            SetDown(to, v);
            int val, cnt;
            Maximize(ray[v], {(val = ray[to][0].first + 1), (cnt = ray[to][0].second/*1*/)});
            if (val) dists[v].push_back({val, cnt});
        }
}
void SetUp(int v, int par)
{
    for (int to: nei[v])
        if (to != par)
        {
            // Set up[to].
            int val = 0, cnt = 0;
            if (ray[v][0].first == ray[to][0].first + 1 && ray[v][0].second == ray[to][0].second)
                Maximize(ray[to], {(val = ray[v][1].first + 1), (cnt = ray[v][1].second/*1*/)});
            else if (ray[v][0].first == ray[to][0].first + 1)
                Maximize(ray[to], {(val = ray[v][0].first + 1), (cnt = ray[v][0].second - ray[to][0].second/*1*/)});
            else
                Maximize(ray[to], {(val = ray[v][0].first + 1), (cnt = ray[v][0].second)});
            if (val) dists[to].push_back({val, cnt});
            SetUp(to, v);
        }
    sort(dists[v].begin(), dists[v].end(), greater<pair<int, int>>());
#ifdef DEBUG
    cerr << "v: " << v << "\tdists: " << dists[v][0] << ' ';
    if (dists[v].size() >= 2) cout << dists[v][1];
    if (dists[v].size() >= 3) cout << ' ' << dists[v][2];
    cout << endl;
#endif
    if (dists[v].size() < 3) return;
    bool eq = (dists[v][1].first == dists[v][2].first);
    int cnt[2];
    for (int i = 0; i < 3; ++i)
    {
        if (ray[v][i].first == dists[v][1].first)
            cnt[0] = ray[v][i].second;
        if (ray[v][i].first == dists[v][2].first)
            cnt[1] = ray[v][i].second;
    }
    llong delta;
    if (eq)
        ans[dists[v][0].first * (dists[v][1].first + dists[v][2].first)] += (delta = (cnt[0] * (cnt[0] - 1LL)) / 2LL);
    else
        ans[dists[v][0].first * (dists[v][1].first + dists[v][2].first)] += (delta = (llong)cnt[0] * cnt[1]);
    // Subtract x * (x - 1) / 2 for x = rays going to the same `to`
    for (auto p: dists[v])
    {
        llong dlt;
        if ((p.first == dists[v][1].first || p.first == dists[v][2].first) && dists[v][1].first == dists[v][2].first) // erkrord paymany petqa?
        {
            bool f = (p.first == dists[v][0].first);
            if (f) --p.second;
            ans[dists[v][0].first * (dists[v][1].first + dists[v][2].first)] -=
            (dlt = (p.second * (p.second - 1LL)) / 2LL);
            if (f) ++p.second;
#ifdef DEBUG
            cerr << "v: " << v << "\tdelta = -" << dlt << endl;
#endif
        }
    }
#ifdef DEBUG
    cerr << "v: " << v << "\tdelta = " << delta << endl;
#endif
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    // cin >> n;
    // n = rand() % 20 + 1;
#ifndef STRESS_TESTING
    cin >> n;
#endif
#ifdef STRESS_TESTING
    n = 9;
    int seed;
    cin >> seed;
    srand(seed);
#endif
    // cerr << n << endl;
    for (int i = 1; i < n; ++i)
    {
        int u, v;
#ifndef STRESS_TESTING
        cin >> u >> v;
#else
        v = i + 1;
        u = rand() % i + 1;
        cerr << u << ' ' << v << endl;
#endif
        nei[u].push_back(v);
        nei[v].push_back(u);
    }
    SetDown(1, -1);
    /*for (int v = 1; v <= n; ++v)
        cerr << v << ": " << ray[v][0] << ' ' << ray[v][1] << ' ' << ray[v][2] << endl;*/
    SetUp(1, -1);
#ifdef DEBUG
    for (int v = 1; v <= n; ++v)
    {
        cerr << v << ": " << ray[v][0] << ' ' << ray[v][1] << ' ' << ray[v][2] << endl;
    }
    for (auto it: ans)
        cerr << it << endl;
#endif
    if (ans.size())
        cout << ans.rbegin()->first << ' ' << ans.rbegin()->second;
    else
        cout << "0 1";
#ifdef STRESS_TESTING
    cout << endl;
    AC::Solve(n);
#endif
}
/*
// new
9
1 2
1 3
2 4
3 5
4 6
6 7
3 8
1 9

12 1
12 2 // right answer

// old
9
1 2
2 3
2 4
3 5
2 6
2 7
3 8
7 9

6 9
6 10 // right answer



// old
9
1 2
2 3
3 4
3 5
5 6
4 7
2 8
6 9
12 3
12 2 // right answer
*/

Compilation message (stderr)

road.cpp: In function 'std::pair<int, int> AC::DFS(int, int, int)':
road.cpp:48:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0; i<nei[u].size(); i++)
                       ~^~~~~~~~~~~~~~
road.cpp: In function 'void AC::MaxDist(int)':
road.cpp:71:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0; i<nei[u].size(); i++)
                       ~^~~~~~~~~~~~~~
road.cpp: In function 'void SetUp(int, int)':
road.cpp:157:107: warning: 'cnt[1]' may be used uninitialized in this function [-Wmaybe-uninitialized]
         ans[dists[v][0].first * (dists[v][1].first + dists[v][2].first)] += (delta = (llong)cnt[0] * cnt[1]);
                                                                                                      ~~~~~^
road.cpp:145:9: warning: 'cnt[0]' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int cnt[2];
         ^~~

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