oj.uz

답안 #758210

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
758210 2023-06-14T09:25:56 Z vjudge1 Hard route (IZhO17_road) C++17
0 / 100
 12 ms 19924 KB 
#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], mx3[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;
        if(s.size())
            mx3[x] = *s.begin() * -1;
        ll cnt = 0;
        for(ll i : v[x]) {
            if(d[x] - 1 == d[i]) {
                mx3[x] = max(mx3[x], mx3[i]);
                if(mx_cnt[i].first == mx1)
                    cnt += mx_cnt[i].second;
            }
        }
        if(cnt > 1) {
            if(mx2 != mx1)
                mx3[x] = mx2;
            mx2 = mx1;
            if(cnt > 2)
                mx3[x] = 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;
            }
        }
        y = max(y, mx3[x]);
        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 = 1; i <= n; i++)
        mx3[i] = -1;
    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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19924 KB Output is correct
2 Correct 12 ms 19880 KB Output is correct
3 Correct 11 ms 19924 KB Output is correct
4 Incorrect 11 ms 19924 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19924 KB Output is correct
2 Correct 12 ms 19880 KB Output is correct
3 Correct 11 ms 19924 KB Output is correct
4 Incorrect 11 ms 19924 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19924 KB Output is correct
2 Correct 12 ms 19880 KB Output is correct
3 Correct 11 ms 19924 KB Output is correct
4 Incorrect 11 ms 19924 KB Output isn't correct
5 Halted 0 ms 0 KB -