oj.uz

Submission #758198

# Submission time Handle Problem Language Result Execution time Memory
758198 2023-06-14T09:11:27 Z vjudge1 Hard route (IZhO17_road) C++17
0 / 100
 9 ms 15996 KB 
#include"bits/stdc++.h"
using namespace std;
#define ll long long
const ll mod = 1000000007;

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

void dfs(int x, int par) {
    int mx = 0;
    for(int 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(int x) {
    set<int> s;
    for(int 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 {
        int mx1 = *s.begin() * -1;
        s.erase(s.begin());
        int mx2 = mx1;
        if(s.size())
            mx2 = *s.begin() * -1;
        int cnt = 0;
        for(int i : v[x]) {
            if(mx_cnt[i].first == mx1)
                cnt += mx_cnt[i].second;
        }
        if(cnt > 1)
            mx2 = mx1;
        int y = d[root] - d[x];
        for(int i = 0; i < child[root]; i++) {
            if(vec[i].second != sec[x]) {
                y += vec[i].first;
                break;
            }
        }
        int o = y * (mx1 + mx2);
        vector<pair<int, int>> mx_cnt_v;
        for(int 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());
        int sz = mx_cnt_v.size();
        int pre[sz];
        for(int i = 0; i < sz; i++) {
            pre[i] = mx_cnt_v[i].second;
            if(i)
                pre[i] += pre[i - 1];
        }
        for(int i = 0; i < sz; i++) {
            if(i && mx_cnt_v[i].first != mx_cnt_v[i].first)
                break;
            int 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);

    int n;
    cin >> n;
    for(int i = 0; i < n - 1; i++) {
        int 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(int i = 1; i <= n; i++) {
        if(child[i] > 1) {
            root = i;
            for(int j : v[i])
                sec[j] = j;
            d[i] = 1;
            dfs(i, 0);
            break;
        }
    }
    for(int i : v[root])
        vec.push_back({d[i], i});
    sort(vec.rbegin(), vec.rend());
    dfs2(root);
    int 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

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 9 ms 15996 KB Output is correct
3 Correct 9 ms 15916 KB Output is correct
4 Incorrect 9 ms 15984 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 9 ms 15996 KB Output is correct
3 Correct 9 ms 15916 KB Output is correct
4 Incorrect 9 ms 15984 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 9 ms 15996 KB Output is correct
3 Correct 9 ms 15916 KB Output is correct
4 Incorrect 9 ms 15984 KB Output isn't correct
5 Halted 0 ms 0 KB -