oj.uz

답안 #702898

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
702898 2023-02-25T09:46:50 Z finn__ Hard route (IZhO17_road) C++17
0 / 100
 6 ms 11988 KB 
#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<unsigned, unsigned>> leafs = {{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<unsigned, unsigned>>());

    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() > 1)
        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

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

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Incorrect 6 ms 11988 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Incorrect 6 ms 11988 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Incorrect 6 ms 11988 KB Output isn't correct
5 Halted 0 ms 0 KB -