oj.uz

Submission #948212

# Submission time Handle Problem Language Result Execution time Memory
948212 2024-03-17T22:54:58 Z atom Hard route (IZhO17_road) C++17
0 / 100
 4 ms 13700 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 = 5e5 + 5;
const int INF = 1e9;
int n;
vector <int> adj[N];
ll ans, cnt;
using T = pair <ll, ll>;

T dp[N];
// <maximum distance from current node, number of ways>
void dfs(int u, int p) {
    dp[u] = make_pair(0, 1);
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        if (dp[u].first < dp[v].first + 1)
            dp[u] = make_pair(dp[v].first + 1, dp[v].second);
        else if (dp[u].first == dp[v].first + 1)
            dp[u].second += dp[v].second;
    }
}

void reroot(int u, int p, T pre) {
    vector <T> cand;
    if (u || (int) adj[u].size() == 1)
        cand.push_back(pre);

    for (int v : adj[u]) 
        if (v ^ p)
            cand.push_back(make_pair(dp[v].first + 1, dp[v].second));
    sort(cand.rbegin(), cand.rend());
    
    if ((int) cand.size() > 2) {
        ll hardness = cand[0].first * (cand[1].first + cand[2].first);
        ll cur_cnt = 0;
        ll ways = 0;

        debug(u, p, pre);
        debug(hardness);
        for (auto &[x, y] : cand) if (x == cand[2].first) ++ways;

        // case 1: all distinct values
        if (cand[0].first != cand[1].first && cand[1].first != cand[2].first)
            cur_cnt = cand[1].second * ways;
        // case 2: all same values
        else if (cand[0].first == cand[1].first && cand[1].first == cand[2].first) {
            cur_cnt = (ways - 1) * ways / 2;
        }
        // case 3: first two are the same
        else if (cand[0].first == cand[1].first && cand[1].first != cand[2].first) {
            cur_cnt = (cand[0].second + cand[1].second) * cand[2].second;
        }
        // case 4: last two are the same
        else if (cand[0].first != cand[1].first && cand[1].first == cand[2].first) {
            cur_cnt = (ways - 1) * ways / 2;
        }
        if (ans < hardness) {
            ans = hardness;
            cnt = cur_cnt;
        }
        else if (ans == hardness)
            cnt += cur_cnt;
    }

    // processing two nodes of current subtree;
    T c1, c2;
    for (auto &[x, y] : cand) {
        if (x + 1 > c1.first) {
            c2 = c1;
            c1 = make_pair(x + 1, y);
        }
        else if (x + 1 == c1.first) {
            c1.second += y;
        }
        else if (x + 1 > c2.first) {
            c2 = make_pair(x + 1, y);
        }
        else if (x + 1 == c2.first) {
            c2.second += y;
        }
    }

    for (int v : adj[u]) {
        if (v == p) continue;
        if (dp[v].first + 2 == c1.first) {
            if (dp[v].second == c1.second) // same branch;
                reroot(v, u, c2);
            else
                reroot(v, u, make_pair(c1.first, c1.second - dp[v].second));
        }
        else 
            reroot(v, u, c1);
    }
}

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;
    
    dfs(1, 0);
    reroot(1, 0, {0, 1});

    cout << ans << " " << cnt << "\n";

    return 0;
}

/*
    leaf nodes always product maximum distance?
*/

Compilation message

road.cpp: In function 'void reroot(int, int, T)':
road.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 166
      |                    ^~~
road.cpp:48:9: note: in expansion of macro 'debug'
   48 |         debug(u, p, pre);
      |         ^~~~~
road.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 166
      |                    ^~~
road.cpp:49:9: note: in expansion of macro 'debug'
   49 |         debug(hardness);
      |         ^~~~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13660 KB Output is correct
2 Correct 4 ms 13660 KB Output is correct
3 Correct 3 ms 13700 KB Output is correct
4 Incorrect 3 ms 13696 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13660 KB Output is correct
2 Correct 4 ms 13660 KB Output is correct
3 Correct 3 ms 13700 KB Output is correct
4 Incorrect 3 ms 13696 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13660 KB Output is correct
2 Correct 4 ms 13660 KB Output is correct
3 Correct 3 ms 13700 KB Output is correct
4 Incorrect 3 ms 13696 KB Output isn't correct
5 Halted 0 ms 0 KB -