Submission #1305387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305387		LucasLe	Hard route (IZhO17_road)	C++20	52 / 100	2099 ms	63808 KiB

road

#include <bits/stdc++.h>

const int maxn = 5e5 + 5;

long long mx_len, ways;
int N;
bool is_leaf[maxn + 5];
std::vector<int> G[maxn + 5];
std::pair<std::pair<int, int>, std::pair<int, int>> f[maxn + 5];

void preDFS(int u, int p) {
    if (G[u].size() == 1) {
        is_leaf[u] = true;
    }
    for (int v : G[u]) {
        if (v == p) continue;
        preDFS(v, u);
    }
}

void DFS(int u, int p, int depth) {
    std::pair<int, int> &pf = f[u].first, &ps = f[u].second;
    if (p && G[u].size() == 1) {
        pf = {0, 1};
        ps = {0, 0};
        return;
    }
    
    pf = {0, 0}, ps = {0, 0};
    int x, y, cnt = 0;

    for (int v : G[u]) {
        if (v == p) continue;
        DFS(v, u, depth + 1);

        std::tie(x, y) = f[v].first;
        x++;

        if (x > pf.first) {
            cnt = 1;
            ps = pf;
            pf = {x, y};
        } else if (x == pf.first) {
            cnt++;
            pf.second += y;
        } else if (x > ps.first) {
            ps = {x, y};
        } else if (x == ps.first) {
            ps.second += y;
        }
    }
    
    if (cnt > 1) {
        y = pf.first;
        long long len = 1ll * (depth + y) * y;
        if (len > mx_len) {
            mx_len = len;
            ways = pf.second;
        } else if (len == mx_len) {
            ways += pf.second;
        }
    } else if (ps.second) {
        x = ps.first;
        y = pf.first;
        long long len = 1ll * (depth + x) * y;
        if (len > mx_len) {
            mx_len = len;
            ways = ps.second;
        } else if (len == mx_len) {
            ways += ps.second;
        }
    }
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);

    std::cin >> N;
    for (int i = 1; i < N; ++i) {
        int u, v; std::cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    preDFS(1, 0);
    for (int u = 1; u <= N; ++u) if (is_leaf[u]) {
        DFS(u, 0, 0);
    }

    if (!mx_len) {
        std::cout << 0 << ' ' << 1 << '\n';
    } else {
        std::cout << mx_len << ' ' << ways / 2 << '\n';
    }

    return 0;
}

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