제출 #941423

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
941423		TAhmed33	Hard route (IZhO17_road)	C++98	52 / 100	112 ms	1116 KiB

road

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = -1e9;
const int MAXN = 5e3 + 25;
vector <int> adj[MAXN];
int n;
ll mx = 0, cnt = 1;
pair <ll, ll> dfs (int pos, int par, int dep) {
    if (par != -1 && adj[pos].size() == 1) {
        return {0, 1};
    }
    pair <ll, ll> d1 = {inf, 0}, d2 = {inf, 0};
    pair <ll, ll> ret = {inf, 0};
    bool flag = 0;
    for (auto j : adj[pos]) {
        if (j == par) continue;
        auto h = dfs(j, pos, dep + 1);
       /* if (pos == 1) {
            cout << h.first + 1 << " | " << h.second << '\n';
        }*/
        h.first += 1;
        if (h.first > d1.first) {
            d2 = d1; d1 = h;
        } else if (h.first == d1.first) {
            d1.second += h.second;
        } else if (h.first > d2.first) {
            d2 = h;
        } else if (h.first == d2.first) {
            d2.second += h.second;
        }
        if (h.first > ret.first) {
            ret = h; flag = 0;
        } else if (h.first == ret.first) {
            ret.second += h.second;
            flag = 1;
        }
    }
    if (flag) {
        //cout << pos << "::::\n";
        ll t = (dep + d1.first) * d1.first, s = ret.second;
        if (t > mx) {
            mx = t; cnt = s;
        } else if (t == mx) {
            cnt += s;
        }
        return ret;
    }
    //cout << pos << ":: " << d1.first << " " << d2.first << '\n';
    ll t = (dep + d1.first) * d2.first, s = d1.second;
    //cout << t << " " << s << '\n';
    if (t > mx) {
        mx = t; cnt = s; 
    } else if (t == mx) {
        cnt += s;
    }
    t = (dep + d2.first) * d1.first, s = d2.second;
    //cout << t << " " << s << '\n';
    if (t > mx) {
        mx = t; cnt = s;
    } else if (t == mx) {
        cnt += s;
    }

    return ret;
}
int main () {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) {
        if ((int)adj[i].size() == 1) {
            dfs(i, -1, 0);
        }
        //cout << i << ": " << mx << '\n';
    }
    if (mx == 0) {
        cout << "0 1\n";
        return 0;
    }
    cout << mx << " " << cnt / 2 << '\n';
}

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