oj.uz

Submission #941422

# Submission time Handle Problem Language Result Execution time Memory
941422 2024-03-08T22:05:03 Z TAhmed33 Hard route (IZhO17_road) C++
0 / 100
 0 ms 500 KB 
#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);
        h.first += 1;
        if (h.first > d1.first) {
            d2 = d1; d1 = h;
        } else if (h.first > d2.first) {
            d2 = h;
        }
        if (h.first > ret.first) {
            ret = h;
        } else if (h.first == ret.first) {
            ret.second += h.second;
            flag = 1;
        }
    }
    if (flag) {
        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;
    }

    ll t = (dep + d1.first) * d2.first, s = d1.second;
    if (t > mx) {
        mx = t; cnt = s; 
    } else if (t == mx) {
        cnt += s;
    }
    t = (dep + d2.first) * d1.first, s = d2.second;
    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);
        }
    }
    if (mx == 0) {
        cout << "0 1\n";
        return 0;
    }
    cout << mx << " " << cnt / 2 << '\n';
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 500 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 500 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 500 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -