oj.uz

Submission #938225

# Submission time Handle Problem Language Result Execution time Memory
938225 2024-03-05T03:11:56 Z weakweakweak Papričice (COCI20_papricice) C++17
0 / 110
 3 ms 12892 KB 
//抄解，因為我只會暴力，然後往換根dp想一直想不到(我猜根本不能用換根dp解)
/*
case 1. y is x's ancenstor
有sz[x], sz[y] - sz[x], n - sz[y] 3塊。
無論，誰是最小，我都會希望除了sz[x]以外的兩塊盡量接近。
我們想要abs(sz[y] - sz[x] - (n - sz[u])) = abs(2sz[y] - (n + sz[x])) = 2abs(sz[y] - (n + sz[x]) / 2) 盡量小。
也就等同於想要sz[y]盡量接近(n + sz[x]) / 2

case 2. y isn't x's ancenstor
有sz[x], sz[y], n - sz[x] - sz[y] 3塊
相同的我們希望sz[y]和n - sz[y] - sz[x]盡量接近。
我們想要abs((n - sz[y] - sz[x]) - sz[y]) 盡量小
等同於想要sz[y] 盡量接近(n - sz[x]) / 2
這個case比較顯然一點
*/
#include <bits/stdc++.h>
using namespace std;

multiset<int> anc, nanc;
int n, sz[510000], ans = 10010000;
vector <int> e[510000];

void dfs (int i, int par) {
    sz[i] = 1;
    for (int j : e[i]) if (j != par) {
        dfs(j, i);
        sz[i] += sz[j];
    }
return;}

int get (int x, int y, int z) {
    int mn = min({x, y, z}), mx = max({x, y, z});
    if (mn <= 0) return INT_MAX;
    return mx - mn;
}

void dfs2 (int i, int par) {
    if (anc . size()) {
        auto it = anc.lower_bound((n + sz[i]) / 2);
        if (it != anc.end()) ans = min(ans, get(n - sz[i] - (*it - sz[i]), sz[i], *it - sz[i]));
        if (it != anc.begin()) ans = min(ans, get(n - sz[i] - ((*--it) - sz[i]), sz[i], (*--it) - sz[i]));
    }
    if (nanc . size()) {
        auto it = nanc.lower_bound((n - sz[i]) / 2);
        if (it != nanc.end()) ans = min(ans, get(n - sz[i] - *it, *it, sz[i]));
        if (it != nanc.begin()) ans = min(ans, get(n - sz[i] - *--it, *--it, sz[i]));
    }
    anc . insert(sz[i]);
    for (int j : e[i]) if (j != par) dfs2(j, i);
    nanc . insert(sz[i]);
    anc . erase(anc.find(sz[i]));
}


signed main () {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for (int i = 2, x, y; i <= n; i++) {
        cin >> x >> y;
        e[x] . push_back(y);
        e[y] . push_back(x);
    }

    dfs(1, 1);

    dfs2(1, 1);

    cout << ans << '\n';
return 0;}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Incorrect 3 ms 12888 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Incorrect 3 ms 12888 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Incorrect 3 ms 12888 KB Output isn't correct
4 Halted 0 ms 0 KB -