Submission #175172

#	Time	Username	Problem	Language	Result	Execution time	Memory
175172		srvlt	Hard route (IZhO17_road)	C++14	0 / 100	36 ms	35704 KiB

road

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree <pair <int, int>, null_type, less <pair <int, int> >, rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;

#define ll long long
#define db double
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mp make_pair
#define size(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

#define endl "\n"
#define int long long

using namespace std;

void dout() {
    cerr << endl;
}
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;

const int N = 5e5 + 7;
int n, root = -1, deg[N], h[N];
int num[N], up[N];
vector <int> q[N], p[N], s[N];

void prep(int v, int par) {
    int child = 0;
    p[v].pb(0);
    for (auto i : q[v]) {
        if (i == par) {
            continue;
        }
        h[i] = h[v] + 1;
        prep(i, v);
        child++;
        p[v].pb(max(p[v].back(), p[i][size(q[i]) - 1]));
        num[i] = child;
    }
    for (int i = 0; i <= child + 1; i++) {
        s[v].pb(0);
    }
    for (int i = size(q[v]) - 1; i >= 0; i--) {
        int to = q[v][i];
        if (to == par) {
            continue;
        }
        s[v][child] = max(s[v][child + 1], p[to][size(q[to]) - 1]);
        child--;
    }
    if (child == 0) {
        p[v][0] = s[v][0] = h[v];
    }
}

int get(int v, int par) {
    if (v == root) {
        return 0;
    }
    return max(p[par][num[v] - 1], s[par][num[v] + 1]);
}

multiset <pii> st;
pii tmp;

void add(int x) {
    auto it = st.lower_bound({x, 0});
    if (it == st.end() || (*it).fi != x) {
        st.insert({x, 1});
    }   else {
        tmp = *it;
        st.erase(it);
        tmp.se++;
        st.insert(tmp);
    }
    if (size(st) > 3) {
        st.erase(st.begin());
    }
}

map <int, int> ans;

void dfs(int v, int par) {
    for (auto i : q[v]) {
        if (i == par) {
            continue;
        }
        up[i] = max(up[v], get(i, v) - h[v]) + 1;
        dfs(i, v);
    }
    for (auto i : q[v]) {
        if (i == par) {
            continue;
        }
        add(p[i][size(q[i]) - 1] - h[v]);
    }
    bool A = false, B = false;
    if (size(st) > 0) {
        auto it = --st.end();
        int d = (*it).fi, cnt = (*it).se;
        if (cnt > 1) {
            ans[d * up[v] * 2] += cnt * (cnt - 1) / 2;
            A = true;
        }
        if (cnt > 2) {
            ans[d * d * 2] += cnt * (cnt - 1) / 2;
            B = true;
        }
        if (size(st) > 1) {
            int d2 = (*prev(it)).fi, cnt2 = (*prev(it)).se;
            if (!A) {
                ans[(d + d2) * up[v]] += cnt * cnt2;
            }
            if (!B && cnt + cnt2 > 2) {
                if (cnt2 == 1) {
                    ans[d * (d2 + d2)] += cnt * cnt2;
                }   else {
                    ans[d * (d2 + d2)] += cnt2 * (cnt2 - 1) / 2;
                }
                B = true;
            }
            if (size(st) > 2) {
                int d3 = (*st.begin()).fi, cnt3 = (*st.begin()).se;
                if (!B) {
                    ans[d * (d2 + d3)] += cnt2 * cnt3;
                }
            }
        }
    }
    st.clear();
}

void solve(int tc) {
    // check for (int i = 0; i < n; j++)
    cin >> n;
    if (n == 2) {
        cout << "0 1";
        return;
    }
    int x, y;
    for (int i = 1; i <= n - 1; i++) {
        cin >> x >> y;
        q[x].pb(y);
        q[y].pb(x);
        deg[x]++;
        deg[y]++;
    }
    for (int i = 1; i <= n; i++) {
        if (deg[i] > 1) {
            root = i;
            break;
        }
    }
    prep(root, -1);
    dfs(root, -1);
    pii res = *(--ans.end());
    cout << res.fi << " " << res.se;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int tc = 1;
//    cin >> tc;
    for (int i = 0; i < tc; i++) {
        solve(i);
//        cleanup();
    }
}

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