Submission #1127816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127816		SeDunion	Hard route (IZhO17_road)	C++20	0 / 100	17 ms	23880 KiB

road

#include <iostream>
#include <vector>

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, 1};

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

int dfs(int v, int p = -1) {
    vector<ll> vec;
    for (int to : g[v]) if (to != p) {
        int cur = dfs(to, v) + 1;
        vec.emplace_back(cur);
    }
    sort(vec.rbegin(), vec.rend());
    if (p == -1) {
        if (vec.size() >= 3) {
            for (int i = 0 ; i < 3 ; ++ i) {
                for (int j = 0 ; j < i ; ++ j) {
                    int k = 3 - i - j;
                    upd(vec[k] * (vec[i] + vec[j]));
                }
            }
        }
    }
    return (!vec.empty() ? vec[0] : 0);
}


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) {
        dfs(i);
    }
    cout << ans.first << ' ' << ans.second << '\n';
}

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