제출 #751739

#제출 시각아이디문제언어결과실행 시간메모리
751739lycheesHard route (IZhO17_road)C++17
100 / 100
754 ms128352 KiB
#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); }

컴파일 시 표준 에러 (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);
      |         ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...