Submission #1127820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127820		SeDunion	Hard route (IZhO17_road)	C++20	52 / 100	2097 ms	96608 KiB

road

#include <iostream>
#include <vector>
#include <math.h>
#include <cmath>

using namespace std;
using pii = pair<int ,int>;
using ll = long long;
using pll = pair<ll, ll>;

const int N = 1e6 + 123;

vector<int> g[N];

pll ans = {0, 2};

void upd(ll x) {
    if (x <= 0) return;
    if (ans.first == x) ans.second++;
    else if (ans.first < x) ans = {x, 1};
}

int h[N];

void precalc(int v, int p = -1) {
    h[v] = 0;
    for (int to : g[v]) if (to != p) {
        precalc(to, v);
        h[v] = max(h[v], h[to] + 1);
    }
}

void dfs(int v, int p = -1, ll x = 0, ll d = 0) {
    vector<ll> vec = {0};
    for (int to : g[v]) if (to != p) {
        vec.push_back(h[to] + 1);
    }
    sort(vec.rbegin(), vec.rend());
    for (int to : g[v]) if (to != p) {
        dfs(to, v, max(x, vec[0] == h[to] + 1 ? vec[1] : vec[0]), d + 1);
    }
    if (g[v].size() == 1) {
        upd(d * x);
    }
}


int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    for (int i = 1 ; i <= n ; ++ i) {
        if (g[i].size() == 1) {
            precalc(i);
            dfs(i);
        }
    }
    cout << ans.first << ' ' << ans.second / 2 << '\n';
}

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