Submission #751739

#	Time	Username	Problem	Language	Result	Execution time	Memory
751739		lychees	Hard route (IZhO17_road)	C++17	100 / 100	754 ms	128352 KiB

road

#include <bits/stdc++.h>
using namespace std;

/*
Every hard route from u to v must have some node x on the path from u to v,
such that the node, that is most distant from the path u -> v meets the path at
x. We go over every node and calculate the maximum hardness of some route where
the node is the mentioned x, and how many of these paths there are.
*/

#define N 500000

vector<unsigned> g[N];
uint64_t d[N], c[N];
uint64_t max_hardness = 0, path_count = 1;

void calc_subtree_height(unsigned u, unsigned p)
{
    d[u] = 0, c[u] = 1;
    for (unsigned const &v : g[u])
    {
        if (v != p)
        {
            calc_subtree_height(v, u);
            if (d[v] + 1 > d[u])
                d[u] = d[v] + 1, c[u] = c[v];
            else if (d[v] + 1 == d[u])
                c[u] += c[v];
        }
    }
}

void calc_maximum_hardness(unsigned u, unsigned p, unsigned pdis, unsigned pcount)
{
    vector<pair<uint64_t, uint64_t>> leafs;
    if (u || g[u].size() == 1)
        leafs.emplace_back(pdis, pcount);
    for (unsigned const &v : g[u])
        if (v != p)
            leafs.emplace_back(d[v] + 1, c[v]);
    sort(leafs.begin(), leafs.end(), greater<pair<uint64_t, uint64_t>>());

    if (leafs.size() >= 3 &&
        leafs[0].first * (leafs[1].first + leafs[2].first) >= max_hardness)
    {
        uint64_t n_eq_to_third = 0,
                 curr_hardness = leafs[0].first * (leafs[1].first + leafs[2].first),
                 curr_paths = 0;
        for (auto const &[dis, num] : leafs)
            if (dis == leafs[2].first)
                n_eq_to_third += num;

        if (leafs[1].first == leafs[2].first)
        {
            curr_paths = n_eq_to_third * n_eq_to_third;
            for (auto const &[dis, num] : leafs) // We cannot pair two paths
                if (dis == leafs[2].first)       // going to the same adj. node.
                    curr_paths -= num * num;
            curr_paths >>= 1;
        }
        else if (leafs[0].first == leafs[1].first)
        {
            curr_paths = (leafs[0].second + leafs[1].second) * n_eq_to_third;
        }
        else
        {
            curr_paths = leafs[1].second * n_eq_to_third;
        }

        if (curr_hardness == max_hardness)
            path_count += curr_paths;
        else
            max_hardness = curr_hardness, path_count = curr_paths;
    }

    uint64_t dis1 = leafs[0].first + 1, num1 = 0, dis2 = 0, num2 = 1;
    if (leafs.size() >= 2)
        dis2 = leafs[1].first + 1, num2 = 0;
    for (auto const &[dis, num] : leafs)
        num1 += num * (dis + 1 == dis1), num2 += num * (dis + 1 == dis2);

    for (unsigned const &v : g[u])
    {
        if (v != p)
        {
            if (d[v] + 2 == dis1 && c[v] == num1)
                calc_maximum_hardness(v, u, dis2, num2);
            else if (d[v] + 2 == dis1)
                calc_maximum_hardness(v, u, dis1, num1 - c[v]);
            else
                calc_maximum_hardness(v, u, dis1, num1);
        }
    }
}

int main()
{
    size_t n;
    scanf("%zu", &n);

    for (size_t i = 0; i < n - 1; i++)
    {
        unsigned u, v;
        scanf("%u %u", &u, &v);
        g[u - 1].push_back(v - 1);
        g[v - 1].push_back(u - 1);
    }

    calc_subtree_height(0, UINT_MAX);
    calc_maximum_hardness(0, UINT_MAX, 0, 1);

    printf("%" PRIu64 " %" PRIu64 "\n", max_hardness, path_count);
}

Compilation message (stderr)

road.cpp: In function 'int main()':
road.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     scanf("%zu", &n);
      |     ~~~~~^~~~~~~~~~~
road.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         scanf("%u %u", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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