| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 751739 |
2023-06-01T11:03:06 Z |
lychees |
Hard route (IZhO17_road) |
C++17 |
|
754 ms |
128352 KB |
#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
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);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 3 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 4 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 5 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 6 |
Correct |
9 ms |
11988 KB |
Output is correct |
| 7 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 8 |
Correct |
6 ms |
12056 KB |
Output is correct |
| 9 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 10 |
Correct |
7 ms |
12044 KB |
Output is correct |
| 11 |
Correct |
9 ms |
11988 KB |
Output is correct |
| 12 |
Correct |
7 ms |
11980 KB |
Output is correct |
| 13 |
Correct |
7 ms |
12056 KB |
Output is correct |
| 14 |
Correct |
8 ms |
12056 KB |
Output is correct |
| 15 |
Correct |
7 ms |
12052 KB |
Output is correct |
| 16 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 17 |
Correct |
8 ms |
12060 KB |
Output is correct |
| 18 |
Correct |
8 ms |
11988 KB |
Output is correct |
| 19 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 20 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 21 |
Correct |
7 ms |
12052 KB |
Output is correct |
| 22 |
Correct |
7 ms |
12076 KB |
Output is correct |
| 23 |
Correct |
7 ms |
12056 KB |
Output is correct |
| 24 |
Correct |
7 ms |
11988 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 3 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 4 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 5 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 6 |
Correct |
9 ms |
11988 KB |
Output is correct |
| 7 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 8 |
Correct |
6 ms |
12056 KB |
Output is correct |
| 9 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 10 |
Correct |
7 ms |
12044 KB |
Output is correct |
| 11 |
Correct |
9 ms |
11988 KB |
Output is correct |
| 12 |
Correct |
7 ms |
11980 KB |
Output is correct |
| 13 |
Correct |
7 ms |
12056 KB |
Output is correct |
| 14 |
Correct |
8 ms |
12056 KB |
Output is correct |
| 15 |
Correct |
7 ms |
12052 KB |
Output is correct |
| 16 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 17 |
Correct |
8 ms |
12060 KB |
Output is correct |
| 18 |
Correct |
8 ms |
11988 KB |
Output is correct |
| 19 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 20 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 21 |
Correct |
7 ms |
12052 KB |
Output is correct |
| 22 |
Correct |
7 ms |
12076 KB |
Output is correct |
| 23 |
Correct |
7 ms |
12056 KB |
Output is correct |
| 24 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 25 |
Correct |
8 ms |
12576 KB |
Output is correct |
| 26 |
Correct |
9 ms |
12652 KB |
Output is correct |
| 27 |
Correct |
10 ms |
12712 KB |
Output is correct |
| 28 |
Correct |
10 ms |
12732 KB |
Output is correct |
| 29 |
Correct |
9 ms |
12704 KB |
Output is correct |
| 30 |
Correct |
10 ms |
12704 KB |
Output is correct |
| 31 |
Correct |
12 ms |
12756 KB |
Output is correct |
| 32 |
Correct |
9 ms |
12576 KB |
Output is correct |
| 33 |
Correct |
9 ms |
12708 KB |
Output is correct |
| 34 |
Correct |
10 ms |
12756 KB |
Output is correct |
| 35 |
Correct |
10 ms |
12760 KB |
Output is correct |
| 36 |
Correct |
9 ms |
12708 KB |
Output is correct |
| 37 |
Correct |
9 ms |
12828 KB |
Output is correct |
| 38 |
Correct |
9 ms |
13140 KB |
Output is correct |
| 39 |
Correct |
9 ms |
12580 KB |
Output is correct |
| 40 |
Correct |
9 ms |
12372 KB |
Output is correct |
| 41 |
Correct |
13 ms |
12328 KB |
Output is correct |
| 42 |
Correct |
9 ms |
12268 KB |
Output is correct |
| 43 |
Correct |
12 ms |
12244 KB |
Output is correct |
| 44 |
Correct |
9 ms |
12328 KB |
Output is correct |
| 45 |
Correct |
9 ms |
12324 KB |
Output is correct |
| 46 |
Correct |
10 ms |
12264 KB |
Output is correct |
| 47 |
Correct |
9 ms |
12372 KB |
Output is correct |
| 48 |
Correct |
9 ms |
12500 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 3 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 4 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 5 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 6 |
Correct |
9 ms |
11988 KB |
Output is correct |
| 7 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 8 |
Correct |
6 ms |
12056 KB |
Output is correct |
| 9 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 10 |
Correct |
7 ms |
12044 KB |
Output is correct |
| 11 |
Correct |
9 ms |
11988 KB |
Output is correct |
| 12 |
Correct |
7 ms |
11980 KB |
Output is correct |
| 13 |
Correct |
7 ms |
12056 KB |
Output is correct |
| 14 |
Correct |
8 ms |
12056 KB |
Output is correct |
| 15 |
Correct |
7 ms |
12052 KB |
Output is correct |
| 16 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 17 |
Correct |
8 ms |
12060 KB |
Output is correct |
| 18 |
Correct |
8 ms |
11988 KB |
Output is correct |
| 19 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 20 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 21 |
Correct |
7 ms |
12052 KB |
Output is correct |
| 22 |
Correct |
7 ms |
12076 KB |
Output is correct |
| 23 |
Correct |
7 ms |
12056 KB |
Output is correct |
| 24 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 25 |
Correct |
8 ms |
12576 KB |
Output is correct |
| 26 |
Correct |
9 ms |
12652 KB |
Output is correct |
| 27 |
Correct |
10 ms |
12712 KB |
Output is correct |
| 28 |
Correct |
10 ms |
12732 KB |
Output is correct |
| 29 |
Correct |
9 ms |
12704 KB |
Output is correct |
| 30 |
Correct |
10 ms |
12704 KB |
Output is correct |
| 31 |
Correct |
12 ms |
12756 KB |
Output is correct |
| 32 |
Correct |
9 ms |
12576 KB |
Output is correct |
| 33 |
Correct |
9 ms |
12708 KB |
Output is correct |
| 34 |
Correct |
10 ms |
12756 KB |
Output is correct |
| 35 |
Correct |
10 ms |
12760 KB |
Output is correct |
| 36 |
Correct |
9 ms |
12708 KB |
Output is correct |
| 37 |
Correct |
9 ms |
12828 KB |
Output is correct |
| 38 |
Correct |
9 ms |
13140 KB |
Output is correct |
| 39 |
Correct |
9 ms |
12580 KB |
Output is correct |
| 40 |
Correct |
9 ms |
12372 KB |
Output is correct |
| 41 |
Correct |
13 ms |
12328 KB |
Output is correct |
| 42 |
Correct |
9 ms |
12268 KB |
Output is correct |
| 43 |
Correct |
12 ms |
12244 KB |
Output is correct |
| 44 |
Correct |
9 ms |
12328 KB |
Output is correct |
| 45 |
Correct |
9 ms |
12324 KB |
Output is correct |
| 46 |
Correct |
10 ms |
12264 KB |
Output is correct |
| 47 |
Correct |
9 ms |
12372 KB |
Output is correct |
| 48 |
Correct |
9 ms |
12500 KB |
Output is correct |
| 49 |
Correct |
601 ms |
74828 KB |
Output is correct |
| 50 |
Correct |
559 ms |
80884 KB |
Output is correct |
| 51 |
Correct |
574 ms |
86036 KB |
Output is correct |
| 52 |
Correct |
503 ms |
67696 KB |
Output is correct |
| 53 |
Correct |
429 ms |
83976 KB |
Output is correct |
| 54 |
Correct |
466 ms |
90624 KB |
Output is correct |
| 55 |
Correct |
425 ms |
74240 KB |
Output is correct |
| 56 |
Correct |
468 ms |
81364 KB |
Output is correct |
| 57 |
Correct |
481 ms |
89680 KB |
Output is correct |
| 58 |
Correct |
484 ms |
82956 KB |
Output is correct |
| 59 |
Correct |
475 ms |
82784 KB |
Output is correct |
| 60 |
Correct |
510 ms |
79496 KB |
Output is correct |
| 61 |
Correct |
754 ms |
128352 KB |
Output is correct |
| 62 |
Correct |
741 ms |
112676 KB |
Output is correct |
| 63 |
Correct |
674 ms |
67332 KB |
Output is correct |
| 64 |
Correct |
676 ms |
56472 KB |
Output is correct |
| 65 |
Correct |
685 ms |
49564 KB |
Output is correct |
| 66 |
Correct |
654 ms |
45940 KB |
Output is correct |
| 67 |
Correct |
682 ms |
43952 KB |
Output is correct |
| 68 |
Correct |
655 ms |
43160 KB |
Output is correct |
| 69 |
Correct |
641 ms |
42912 KB |
Output is correct |
| 70 |
Correct |
636 ms |
42748 KB |
Output is correct |
| 71 |
Correct |
612 ms |
42620 KB |
Output is correct |
| 72 |
Correct |
625 ms |
42784 KB |
Output is correct |
| 73 |
Correct |
636 ms |
43056 KB |
Output is correct |
| 74 |
Correct |
644 ms |
43428 KB |
Output is correct |
| 75 |
Correct |
617 ms |
43968 KB |
Output is correct |
| 76 |
Correct |
553 ms |
45136 KB |
Output is correct |
| 77 |
Correct |
480 ms |
47628 KB |
Output is correct |
| 78 |
Correct |
320 ms |
53036 KB |
Output is correct |
