Submission #1160904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160904		MisterReaper	Hard route (IZhO17_road)	C++20	100 / 100	370 ms	125204 KiB

road

#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    std::cin >> N;
    std::vector<std::vector<int>> adj(N);
    for (int i = 1; i < N; ++i) {
        int A, B;
        std::cin >> A >> B;
        --A, --B;
        adj[A].emplace_back(B);
        adj[B].emplace_back(A);
    }

    std::vector<int> h(N), cnt(N, 1);
    auto dfs1 = [&](auto&& self, int v, int pr) -> void {
        for (auto u : adj[v]) {
            if (u == pr) {
                continue;
            }
            self(self, u, v);
            if (h[u] + 1 > h[v]) {
                h[v] = h[u] + 1;
                cnt[v] = cnt[u];
            } else if (h[u] + 1 == h[v]) {
                cnt[v] += cnt[u];
            }
        }
    };
    dfs1(dfs1, 0, 0);

    i64 ansval = 0, anscpth = 1;
    auto dfs2 = [&](auto&& self, int v, int pr, int hpr, int cntpr) -> void {
        std::vector<std::array<int, 2>> paths;
        if (v > 0 || adj[v].size() == 1) {
            paths.push_back({hpr, cntpr});
        }
        for (auto u : adj[v]) {
            if (u == pr) {
                continue;
            }
            paths.push_back({h[u] + 1, cnt[u]});
        }

        if (adj[v].size() >= 3) {
            std::sort(paths.begin(), paths.end(), std::greater());
            debug(v, paths);
            i64 a = paths[0][0];
            i64 b = paths[1][0];
            i64 c = paths[2][0];
            i64 val = a * (b + c);
            i64 cpth = 0;
            i64 tie = 0;
            for (auto[x, y] : paths) {
                if (x == c) {
                    tie += y;
                }
            }
            if (a == b && b == c) {
                cpth = tie * tie;
                for (auto[x, y] : paths) {
                    if (x == c) {
                        cpth -= y * y;
                    }
                }
                cpth /= 2;
            } else if (a == b) {
                cpth = (paths[0][1] + paths[1][1]) * tie;
            } else if (b == c) {
                cpth = tie * tie;
                for (auto[x, y] : paths) {
                    if (x == c) {
                        cpth -= y * y;
                    }
                }
                cpth /= 2;
            } else {
                cpth = paths[1][1] * tie;
            }
            if (val > ansval) {
                ansval = val;
                anscpth = cpth;
            } else if (val == ansval) {
                anscpth += cpth;
            }
        }

        int longest1 = -1, longest2 = -1;
        int cntlong1 = 0, cntlong2 = 0;
        for (auto[x, y] : paths) {
            x++;
            if (x > longest1) {
                longest2 = longest1;
                cntlong2 = cntlong1;
                longest1 = x;
                cntlong1 = y;
            } else if (x == longest1) {
                cntlong1 += y;
            } else if (x > longest2) {
                longest2 = x;
                cntlong2 = y;
            } else if (x == longest2) {
                cntlong2 += y;
            }
        }

        for (auto u : adj[v]) {
            if (u == pr) {
                continue;
            }
            if (h[u] + 2 == longest1) {
                if (cnt[u] == cntlong1) {
                    self(self, u, v, longest2, cntlong2);
                } else {
                    self(self, u, v, longest1, cntlong1 - cnt[u]);
                }
            } else {
                self(self, u, v, longest1, cntlong1);
            }
        }
    };
    dfs2(dfs2, 0, 0, 0, 1);

    std::cout << ansval << ' ' << anscpth << '\n';

    return 0;
}

• Subtask 1: 19 / 19
• Subtask 2: 33 / 33
• Subtask 3: 48 / 48