Submission #1043020

#TimeUsernameProblemLanguageResultExecution timeMemory
1043020pubin06Hard route (IZhO17_road)C++14
100 / 100
451 ms206432 KiB
#include <bits/stdc++.h> #define int long long #define fi first #define se second #define sz(v) (int)(v).size() #define pii pair<int, int> using namespace std; const int MXn = 500005; void make_better(int &A, int &B, int x, int y) { if (A < x) { A = x; B = y; } else if (A == x) { B += y; } } pii get_better(int A, int B, int x, int y) { if (A < x) { A = x; B = y; } else if (A == x) { B += y; } return {A, B}; } int n; vector<int> adj[MXn]; int mx[MXn], cnt[MXn]; void DFS1(int u, int par) { mx[u] = 0, cnt[u] = 1; for (int v: adj[u]) if (v != par) { DFS1(v, u); make_better(mx[u], cnt[u], mx[v] + 1, cnt[v]); } } int H = 0, dem = 1; void DFS2(int u, int par, int Mx, int Cnt) { vector<tuple<int, int, int>> nah; vector<pii> paths; if (Mx) { paths.emplace_back(Mx, Cnt); } for (int v: adj[u]) if (v != par) { nah.emplace_back(v, mx[v] + 1, cnt[v]); paths.emplace_back(mx[v] + 1, cnt[v]); } sort(begin(paths), end(paths), greater<pii>()); if (sz(paths) >= 3) { int z = paths[0].fi, y = paths[1].fi, x = paths[2].fi; int h = z * (x + y); // cerr << u << ' ' << h; if (H <= h) { int Dz = paths[0].se, Dy = paths[1].se, Dx = paths[2].se; // cerr << ' ' << Dx << ' ' << Dy << ' ' << Dz; int Dem = 0; if (x < y && y < z) { for (int i = 3; i < sz(paths); i++) if (paths[i].fi == x) Dx += paths[i].se; Dem = Dx * Dy; } else if (x == y && y < z) { // Dem = ((Dx + Dy) * (Dx + Dy - 1) / 2) - Dx * (Dx - 1) / 2 - Dy * (Dy - 1) / 2; Dem = Dy * Dx; int tmp = Dy + Dx; for (int i = 3; i < sz(paths); i++) if (paths[i].fi == x) { Dem += tmp * paths[i].se; tmp += paths[i].se; } } else if (x < y && y == z) { for (int i = 3; i < sz(paths); i++) if (paths[i].fi == x) Dx += paths[i].se; Dem = Dx * (Dy + Dz); } else if (x == y && y == z) { Dem = Dz * Dy + (Dz + Dy) * Dx; int tmp = Dx + Dy + Dz; for (int i = 3; i < sz(paths); i++) if (paths[i].fi == x) { Dem += tmp * paths[i].se; tmp += paths[i].se; } } make_better(H, dem, h, Dem); } // cerr << '\n'; } vector<pii> s; if (sz(nah)) { s.resize(sz(nah)); s.back() = {(get<1>(nah.back())) + 1, get<2>(nah.back())}; for (int i = sz(nah) - 2; i >= 0; i--) { s[i] = get_better(s[i + 1].fi, s[i + 1].se, (get<1>(nah[i])) + 1, get<2>(nah[i])); } } pii p = {Mx + 1, Cnt}; for (int i = 0; i < sz(nah); i++) { pii New = p; if (i != sz(nah) - 1) New = get_better(New.fi, New.se, s[i + 1].fi, s[i + 1].se); DFS2(get<0>(nah[i]), u, New.fi, New.se); p = get_better(p.fi, p.se, (get<1>(nah[i])) + 1, get<2>(nah[i])); } } signed main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for (int i = 1, u, v; i < n; i++) { cin >> u >> v; adj[u].emplace_back(v); adj[v].emplace_back(u); } DFS1(1, 0); DFS2(1, 0, 0, 1); cout << H << ' ' << dem; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...