Submission #758200

#	Time	Username	Problem	Language	Result	Execution time	Memory
758200		vjudge1	Hard route (IZhO17_road)	C++17	0 / 100	11 ms	19924 KiB

road

#include"bits/stdc++.h"
using namespace std;
#define ll long long
const ll mod = 1000000007;

vector<ll> v[500001];
vector<pair<ll, ll>> vec, mx_cnt(500001);
ll d[500001], child[500001], sec[500001];
ll root;
map<ll, ll> mp;

void dfs(ll x, ll par) {
    ll mx = 0;
    for(ll i : v[x]) {
        if(i != par) {
            if(sec[x])
                sec[i] = sec[x];
            dfs(i, x);
            mx = max(mx, d[i]);
        }
    }
    d[x] = mx + 1;
}

void dfs2(ll x) {
    set<ll> s;
    for(ll i : v[x]) {
        if(d[x] - 1 == d[i]) {
            dfs2(i);
            s.insert(-mx_cnt[i].first);
        }
    }
    if(child[x] == 1)
        mx_cnt[x] = {1, 1};
    else {
        ll mx1 = *s.begin() * -1;
        s.erase(s.begin());
        ll mx2 = mx1;
        if(s.size())
            mx2 = *s.begin() * -1;
        ll cnt = 0;
        for(ll i : v[x]) {
            if(mx_cnt[i].first == mx1)
                cnt += mx_cnt[i].second;
        }
        if(cnt > 1)
            mx2 = mx1;
        ll y = d[root] - d[x];
        for(ll i = 0; i < child[root]; i++) {
            if(vec[i].second != sec[x]) {
                y += vec[i].first;
                break;
            }
        }
        ll o = y * (mx1 + mx2);
        vector<pair<ll, ll>> mx_cnt_v;
        for(ll i : v[x]) {
            if(d[x] - 1 == d[i] && mx_cnt[i].first >= mx2)
                mx_cnt_v.push_back(mx_cnt[i]);
        }
        sort(mx_cnt_v.begin(), mx_cnt_v.end());
        ll sz = mx_cnt_v.size();
        ll pre[sz];
        for(ll i = 0; i < sz; i++) {
            pre[i] = mx_cnt_v[i].second;
            if(i)
                pre[i] += pre[i - 1];
        }
        for(ll i = 0; i < sz; i++) {
            if(i && mx_cnt_v[i].first != mx_cnt_v[i].first)
                break;
            ll sum = pre[sz - 1] - pre[i];
            if(sum)
                mp[o] += sum;
        }
        mx_cnt[x] = {mx1, cnt};
    }
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    ll n;
    cin >> n;
    for(ll i = 0; i < n - 1; i++) {
        ll a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
        child[a]++, child[b]++;
    }
    if(n == 2) {
        cout << 0 << " " << 1;
        return 0;
    }
    for(ll i = 1; i <= n; i++) {
        if(child[i] > 1) {
            root = i;
            for(ll j : v[i])
                sec[j] = j;
            dfs(i, 0);
            break;
        }
    }
    for(ll i : v[root])
        vec.push_back({d[i], i});
    sort(vec.rbegin(), vec.rend());
    dfs2(root);
    ll mx = 0, ans = 0;
    for(auto i : mp) {
        if(i.first > mx)
            mx = i.first, ans = i.second;
    }
    if(!mx) {
        cout << 0 << " " << 1;
        return 0;
    }
    cout << mx << " " << ans;

    return 0;
}

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