Submission #172268

#	Time	Username	Problem	Language	Result	Execution time	Memory
172268		emil_physmath	Hard route (IZhO17_road)	C++17	19 / 100	31 ms	24568 KiB

road

// #define DEBUG
#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<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;
            Maximize(ray[v], {(val = ray[to][0].first + 1), ray[to][0].second/*1*/});
            if (val) dists[v].push_back(val);
        }
}
void SetUp(int v, int par)
{
    for (int to: nei[v])
        if (to != par)
        {
            // Set up[to].
            int val = 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), 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), ray[v][0].second - ray[to][0].second/*1*/});
            else
                Maximize(ray[to], {(val = ray[v][0].first + 1), ray[v][0].second});
            if (val) dists[to].push_back(val);
            SetUp(to, v);
        }
    sort(dists[v].begin(), dists[v].end(), greater<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] == dists[v][2]);
    int cnt[2];
    for (int i = 0; i < 3; ++i)
    {
        if (ray[v][i].first == dists[v][1])
            cnt[0] = ray[v][i].second;
        if (ray[v][i].first == dists[v][2])
            cnt[1] = ray[v][i].second;
    }
    if (eq)
        ans[dists[v][0] * (dists[v][1] + dists[v][2])] += (cnt[0] * (cnt[0] - 1)) / 2;
    else
        ans[dists[v][0] * (dists[v][1] + dists[v][2])] += cnt[0] * cnt[1];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    // cin >> n;
    // n = rand() % 20 + 1;
    cin >> n;
    /*int seed;
    cin >> seed;
    srand(seed);
    cerr << n << endl;*/
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        cin >> u >> v;
        /*v = i + 1;
        u = rand() % i + 1;
        cerr << u << ' ' << v << endl;*/
        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";
    // cout << endl;
    // AC::Solve(n);
}
/*
8
1 2
1 3
1 4
2 5
4 6
1 7
2 8

6 5
6 7 // right answer
*/

Compilation message (stderr)

road.cpp: In function 'std::pair<int, int> AC::DFS(int, int, int)':
road.cpp:47: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:70: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:155:66: warning: 'cnt[1]' may be used uninitialized in this function [-Wmaybe-uninitialized]
         ans[dists[v][0] * (dists[v][1] + dists[v][2])] += cnt[0] * cnt[1];
                                                           ~~~~~~~^~~~~~~~
road.cpp:155:66: warning: 'cnt[0]' may be used uninitialized in this function [-Wmaybe-uninitialized]

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