oj.uz

Submission #938231

# Submission time Handle Problem Language Result Execution time Memory
938231 2024-03-05T03:18:19 Z weakweakweak Papričice (COCI20_papricice) C++17
110 / 110
 164 ms 34048 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.upper_bound((n + sz[i]) / 2);
        if (it != anc.end()) ans = min(ans, get(n - *it, sz[i], *it - sz[i]));
        if (it != anc.begin()) ans = min(ans, get(n - *--it, sz[i], *prev(it) - sz[i]));
    }
    if (nanc . size()) {
        auto it = nanc.upper_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] - *prev(it), *prev(it), sz[i]));
    }
    anc . insert(sz[i]);
    for (int j : e[i]) if (j != par) dfs2(j, i);
    nanc . insert(sz[i]);
    anc . erase(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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 3 ms 12900 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 3 ms 12900 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 3 ms 13144 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 4 ms 12908 KB Output is correct
9 Correct 4 ms 12888 KB Output is correct
10 Correct 4 ms 12892 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 3 ms 12900 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 3 ms 13144 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 4 ms 12908 KB Output is correct
9 Correct 4 ms 12888 KB Output is correct
10 Correct 4 ms 12892 KB Output is correct
11 Correct 138 ms 29012 KB Output is correct
12 Correct 164 ms 28928 KB Output is correct
13 Correct 118 ms 29468 KB Output is correct
14 Correct 126 ms 29264 KB Output is correct
15 Correct 145 ms 28756 KB Output is correct
16 Correct 118 ms 29816 KB Output is correct
17 Correct 134 ms 29024 KB Output is correct
18 Correct 157 ms 34048 KB Output is correct
19 Correct 142 ms 28964 KB Output is correct
20 Correct 160 ms 28776 KB Output is correct