Submission #854595

#	Time	Username	Problem	Language	Result	Execution time	Memory
854595		The_Samurai	Hard route (IZhO17_road)	C++17	52 / 100	2050 ms	56900 KiB

road

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int inf = 1e9, N = 1e6 + 5;

int root;
ll ans = -1, cnt = 0;
vector<vector<int>> g;
vector<int> longest;
vector<bool> vis;

void dfs1(int u) {
    longest[u] = vis[u] = true;
    for (int v: g[u]) {
        if (!vis[v]) {
            dfs1(v);
            longest[u] = max(longest[u], longest[v] + 1);
        }
    }
}

void dfs2(int u, int mx, int dist) {
    int mx1 = mx, mx2 = 0;
    vis[u] = true;
    for (int v: g[u]) {
        if (vis[v]) continue;
        if (mx1 < longest[v]) {
            mx2 = mx1;
            mx1 = longest[v];
        } else {
            mx2 = max(mx2, longest[v]);
        }
    }
    for (int v: g[u]) {
        if (!vis[v]) {
            if (mx1 == longest[v]) dfs2(v, mx2, dist + 1);
            else dfs2(v, mx1, dist + 1);
        }
    }
    if (g[u].size() == 1 and u != root) {
        if (ans < 1ll * dist * mx) {
            ans = 1ll * dist * mx;
            cnt = 1;
        } else if (ans == 1ll * dist * mx) {
            cnt++;
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
//    freopen("game.in", "r", stdin);
//    freopen("game.out", "w", stdout);
#endif

    int n;
    cin >> n;
    g.assign(n + 1, {});
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    for (int i = 1; i <= n; i++) {
        if (g[i].size() > 1) continue;
        root = i;
        longest.assign(n + 1, 0);
        vis.assign(n + 1, false);
        dfs1(i);
        vis.assign(n + 1, false);
        dfs2(i, 0, 0);
    }
    cout << ans << ' ' << cnt / 2;
}

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