oj.uz

Submission #947491

# Submission time Handle Problem Language Result Execution time Memory
947491 2024-03-16T09:44:43 Z atom Hard route (IZhO17_road) C++17
0 / 100
 1 ms 500 KB 
#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

const int N = 5e3 + 5;
int n;
vector <int> adj[N];
ll ans, cnt;
using T = pair <ll, ll>;
const int INF = 1e9;

T dfs(int u, int p, int dep) {
    if (p != u && (int) adj[u].size() == 1) return make_pair(0, 1);

    T c1, c2, mx; // c1, c2 - two distinct dis : <max_dis, ways>, ans - max_dis of current node
    c1 = c2 = mx = make_pair(-INF, 0);

    bool exit = false;
    for (int v : adj[u]) {
        if (v == p) continue;

        T cur = dfs(v, u, dep + 1);
        cur.first++;

        if (cur.first > c1.first) {
            c2 = c1;
            c1 = cur;
        }
        else if (cur.first == c1.first) {
            c1.second += cur.second;
        }
        else if (cur.first > c2.first) {
            c2 = cur;
        }
        else if (cur.first == c2.first) {
            c2.second += cur.second;
        }

        if (cur.first > mx.first) {
            mx = cur;
        }
        else if (cur.first == mx.first) {
            mx.second += cur.second;
            exit = true;
        }
    }
    // c2 not exist? 
    debug(u, p, c1, c2, mx, ans, cnt, exit);
    if (exit) { // c1 = mx = cur
        ll dis = (dep + c1.first), h = c1.first;
        if (ans < h * dis) {
            ans = h * dis;
            cnt = mx.second;
        }
        else if (ans == h * dis) 
            cnt += mx.second;
        return mx;
    }
    
    ll dis, h;
    dis = (dep + c1.first);
    h = c2.first;
    if (ans < h * dis) {
        ans = h * dis;
        cnt = c1.second;
    }
    else if (ans == h * dis) {
        cnt += c1.second;
    }
    dis = (dep + c2.first);
    h = c1.first;
    if (ans < h * dis) {
        ans = h * dis;
        cnt = c2.second;
    }
    else if (ans == h * dis)
        cnt += c2.second;
    
    return mx;
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);

    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    //sub2: O(n^2)
    ans = 0, cnt = 1;
    for (int u = 1; u <= n; ++u) {
        if ((int) adj[u].size() == 1) {
            dfs(u, u, 0);
        }
    }
    if (ans == 0) {
        cout << ans << " " << 1 << "\n"; // tree = array
        return 0;
    }

    cout << ans << " " << (cnt / 2) << "\n";

    return 0;
}

Compilation message

road.cpp: In function 'T dfs(int, int, int)':
road.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 166
      |                    ^~~
road.cpp:55:5: note: in expansion of macro 'debug'
   55 |     debug(u, p, c1, c2, mx, ans, cnt, exit);
      |     ^~~~~

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 1 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 1 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 1 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 -