| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 702898 |
2023-02-25T09:46:50 Z |
finn__ |
Hard route (IZhO17_road) |
C++17 |
|
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);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
