oj.uz

Submission #938230

# Submission time Handle Problem Language Result Execution time Memory
938230 2024-03-05T03:16:40 Z weakweakweak Papričice (COCI20_papricice) C++17
110 / 110
 169 ms 36708 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 - *prev(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 2 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 12892 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 2 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 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 4 ms 13144 KB Output is correct
7 Correct 4 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 13032 KB Output is correct
10 Correct 5 ms 13144 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 4 ms 13144 KB Output is correct
7 Correct 4 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 13032 KB Output is correct
10 Correct 5 ms 13144 KB Output is correct
11 Correct 139 ms 31424 KB Output is correct
12 Correct 169 ms 31376 KB Output is correct
13 Correct 120 ms 31828 KB Output is correct
14 Correct 136 ms 31456 KB Output is correct
15 Correct 143 ms 31316 KB Output is correct
16 Correct 108 ms 31184 KB Output is correct
17 Correct 137 ms 31316 KB Output is correct
18 Correct 162 ms 36708 KB Output is correct
19 Correct 126 ms 31572 KB Output is correct
20 Correct 150 ms 31360 KB Output is correct