Submission #934771

#	Time	Username	Problem	Language	Result	Execution time	Memory
934771		eysbutno	Hard route (IZhO17_road)	C++17	19 / 100	2 ms	1112 KiB

road

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define f first 
#define s second 

template<class T> bool smin(T& a, T b) {
    return b < a ? a = b, 1 : 0;
}
template<class T> bool smax(T& a, T b) {
    return b > a ? a = b, 1 : 0;
}
int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n; cin >> n;
    vector adj(n, vector<int>());
    for (int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        adj[--x].push_back(--y);
        adj[y].push_back(x);
    }
    vector<int> d(n), c(n);
    auto dfs = [&](int u, int p, auto&& dfs) -> void {
        d[u] = 0, c[u] = 1;
        for (int v : adj[u]) if (v != p) {
            dfs(v, u, dfs);
            if (smax(d[u], d[v] + 1)) {
                c[u] = c[v];
            } else if (d[v] + 1 == d[u]) {
                c[u] += c[v];
            }
        }
    }; dfs(0, -1, dfs);
    ll hard = 0, cnt = 1;
    auto dfs2 = [&](int u, int p, int pd, int pc, 
                    auto&& dfs2) -> void {
        vector<pii> opt;
        if (u > 0 || sz(adj[u]) == 1) {
            opt.push_back({pd, pc});
        }
        for (int v : adj[u]) if (v != p) {
            opt.push_back({d[v] + 1, c[v]});
        }
        sort(all(opt), greater<>());
        if (sz(adj[u]) >= 3) { // can form nonzero path
            ll cur = opt[0].f * (opt[1].f + opt[2].f), 
               num = 0;
            int ties = 0; // equal to third element
            for (auto [k, v] : opt) {
                if (k == opt[2].f) ties += v;
            }
            // case 1: all are distinct
            if (opt[0].f != opt[1].f &&
                opt[1].f != opt[2].f) {
                // num = opt[0].s * opt[1].s * ties;
                num = opt[1].s * ties;
            }
            // case 2: all are the same
            else if (opt[0].f == opt[1].f &&
                opt[1].f == opt[2].f) {
                // n choose 2, in this case
                num = ties * (ties - 1) / 2;
            }
            // case 3: first two are the same
            else if (opt[0].f == opt[1].f) {
                num = (opt[0].s + opt[1].s) * ties;
            }
            // case 4: last two are the same
            else {
                num = ties * (ties - 1) / 2;
            }
            if (smax(hard, cur)) {
                cnt = num;
            } else if (hard == cur) {
                cnt += num;
            }
        }
        // processing parent dist & parent count
        int l1 = 0, l2 = 0, cnt1 = 0, cnt2 = 0;
        for (auto [k, v] : opt) {
            // all paths will increase by len 1
            if (k + 1 > l1) {
                swap(l1, l2), swap(cnt1, cnt2);
                l1 = k + 1, cnt1 = v;
            } else if (k + 1 == l1) {
                cnt1 += v;
            } else if (k + 1 > l2) {
                l2 = k + 1, cnt2 = v;
            } else if (k + 1 == l2) {
                cnt2 += v;
            }
        }
        for (int v : adj[u]) if (v != p) {
            if (d[v] + 2 == l1) {
                (c[v] == cnt1) ? dfs2(v, u, l2, cnt2, dfs2) :
                            	 dfs2(v, u, l1, cnt1 - c[v], dfs2);
            } else {
                dfs2(v, u, l1, cnt1, dfs2);
            }
        }
    }; dfs2(0, -1, 0, 1, dfs2);
    cout << hard << ' ' << cnt << '\n';
}

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