| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 934772 | eysbutno | Hard route (IZhO17_road) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define int long long // NOOOO
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define f first
#define s second
template<class T> bool smin(T& a, T b) {
return b < a ? a = b, 1 : 0;
}
template<class T> bool smax(T& a, T b) {
return b > a ? a = b, 1 : 0;
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(0);
int n; cin >> n;
vector adj(n, vector<int>());
for (int i = 1; i < n; i++) {
int x, y; cin >> x >> y;
adj[--x].push_back(--y);
adj[y].push_back(x);
}
vector<int> d(n), c(n);
auto dfs = [&](int u, int p, auto&& dfs) -> void {
d[u] = 0, c[u] = 1;
for (int v : adj[u]) if (v != p) {
dfs(v, u, dfs);
if (smax(d[u], d[v] + 1)) {
c[u] = c[v];
} else if (d[v] + 1 == d[u]) {
c[u] += c[v];
}
}
}; dfs(0, -1, dfs);
ll hard = 0, cnt = 1;
auto dfs2 = [&](int u, int p, int pd, int pc,
auto&& dfs2) -> void {
vector<pii> opt;
if (u > 0 || sz(adj[u]) == 1) {
opt.push_back({pd, pc});
}
for (int v : adj[u]) if (v != p) {
opt.push_back({d[v] + 1, c[v]});
}
sort(all(opt), greater<>());
if (sz(adj[u]) >= 3) { // can form nonzero path
ll cur = opt[0].f * (opt[1].f + opt[2].f),
num = 0;
int ties = 0; // equal to third element
for (auto [k, v] : opt) {
if (k == opt[2].f) ties += v;
}
// case 1: all are distinct
if (opt[0].f != opt[1].f &&
opt[1].f != opt[2].f) {
// num = opt[0].s * opt[1].s * ties;
num = opt[1].s * ties;
}
// case 2: all are the same
else if (opt[0].f == opt[1].f &&
opt[1].f == opt[2].f) {
// n choose 2, in this case
num = ties * (ties - 1) / 2;
}
// case 3: first two are the same
else if (opt[0].f == opt[1].f) {
num = (opt[0].s + opt[1].s) * ties;
}
// case 4: last two are the same
else {
num = ties * (ties - 1) / 2;
}
if (smax(hard, cur)) {
cnt = num;
} else if (hard == cur) {
cnt += num;
}
}
// processing parent dist & parent count
int l1 = 0, l2 = 0, cnt1 = 0, cnt2 = 0;
for (auto [k, v] : opt) {
// all paths will increase by len 1
if (k + 1 > l1) {
swap(l1, l2), swap(cnt1, cnt2);
l1 = k + 1, cnt1 = v;
} else if (k + 1 == l1) {
cnt1 += v;
} else if (k + 1 > l2) {
l2 = k + 1, cnt2 = v;
} else if (k + 1 == l2) {
cnt2 += v;
}
}
for (int v : adj[u]) if (v != p) {
if (d[v] + 2 == l1) {
(c[v] == cnt1) ? dfs2(v, u, l2, cnt2, dfs2) :
dfs2(v, u, l1, cnt1 - c[v], dfs2);
} else {
dfs2(v, u, l1, cnt1, dfs2);
}
}
}; dfs2(0, -1, 0, 1, dfs2);
cout << hard << ' ' << cnt << '\n';
}
/**
* TASK: Hard Route (IZhO).
* Terminals are (obviously) leaves.
* Probably will consider all paths
* from a given LCA (from which the
* longest distance lies on).
*
* So, DFS over every root x, where
* the endpoints and farthest nodes
* can be chosen. NOTE THAT THE PATH
* WILL BE THE TWO SHORTER DISTANCES!
* (Note that using this information,
* you can prove that no (u, v) pair
* will be double counted.)
*/