Submission #702911

#	Time	Username	Problem	Language	Result	Execution time	Memory
702911		finn__	Hard route (IZhO17_road)	C++17	100 / 100	689 ms	128272 KiB

road

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

#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:92:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     scanf("%zu", &n);
      |     ~~~~~^~~~~~~~~~~
road.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         scanf("%u %u", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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