oj.uz

Submission #938244

# Submission time Handle Problem Language Result Execution time Memory
938244 2024-03-05T03:34:34 Z weakweakweak Papričice (COCI20_papricice) C++17
110 / 110
 199 ms 34192 KB 
//抄解，因為我只會暴力，然後往換根dp想一直想不到(我猜根本不能用換根dp解)
//被iterator揍爛
/*
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 3 ms 12888 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 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 3 ms 12888 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 4 ms 12900 KB Output is correct
7 Correct 4 ms 12892 KB Output is correct
8 Correct 4 ms 12912 KB Output is correct
9 Correct 4 ms 12892 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 12888 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 4 ms 12900 KB Output is correct
7 Correct 4 ms 12892 KB Output is correct
8 Correct 4 ms 12912 KB Output is correct
9 Correct 4 ms 12892 KB Output is correct
10 Correct 4 ms 12892 KB Output is correct
11 Correct 157 ms 28844 KB Output is correct
12 Correct 161 ms 28784 KB Output is correct
13 Correct 118 ms 29600 KB Output is correct
14 Correct 151 ms 29588 KB Output is correct
15 Correct 143 ms 28748 KB Output is correct
16 Correct 104 ms 29556 KB Output is correct
17 Correct 144 ms 29008 KB Output is correct
18 Correct 180 ms 34192 KB Output is correct
19 Correct 124 ms 29060 KB Output is correct
20 Correct 199 ms 28752 KB Output is correct