oj.uz

Submission #464419

# Submission time Handle Problem Language Result Execution time Memory
464419 2021-08-13T07:40:33 Z dannyboy20031204 Papričice (COCI20_papricice) C++17
110 / 110
 290 ms 26124 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define double long double
using namespace std;
void db() {cerr << endl;}
template <typename T, typename ...U> void db(T a, U ...b) {
    cerr << a << ' ', db(b...);
}
const int N = 2e5 + 1, inf = 1e9 + 1;
int n, ans = inf;
vector<int> g[N];
int sz[N];
multiset<int> s, s2;
void dfs1(int u, int p){
    sz[u] = 1;
    for (int i : g[u]){
        if (i == p)
            continue;
        dfs1(i, u);
        sz[u] += sz[i];
    }
    //db(u, sz[u]);
}
int f(int a, int b, int c){
    return max({abs(a - b), abs(a - c), abs(b - c)});
}
void dfs(int u, int p){
    auto it = s2.lower_bound((n + sz[u]) / 2);
    if (it != s2.end())
        ans = min(ans, f(sz[u], *it - sz[u], n - *it));
    if (it != s2.begin()){
        --it;
        ans = min(ans, f(sz[u], *it - sz[u], n - *it));
    }

    auto it2 = s.lower_bound((n - sz[u]) / 2);
    if (it2 != s.end())
        ans = min(ans, f(sz[u], *it2, n - *it2 - sz[u]));
    if (it2 != s.begin()){
        --it2;
        ans = min(ans, f(sz[u], *it2, n - *it2 - sz[u]));
    }

    s2.insert(sz[u]);
    for (int i : g[u]){
        if (i == p)
            continue;
        dfs(i, u);
    }
    s.insert(sz[u]);
    s2.erase(s2.lower_bound(sz[u]));
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 0; i < n - 1; i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(1, -1);
    dfs(1, -1);
    cout << ans << '\n';
}

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 4 ms 5156 KB Output is correct
7 Correct 5 ms 5196 KB Output is correct
8 Correct 5 ms 5156 KB Output is correct
9 Correct 4 ms 5196 KB Output is correct
10 Correct 5 ms 5156 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 4 ms 5156 KB Output is correct
7 Correct 5 ms 5196 KB Output is correct
8 Correct 5 ms 5156 KB Output is correct
9 Correct 4 ms 5196 KB Output is correct
10 Correct 5 ms 5156 KB Output is correct
11 Correct 262 ms 21900 KB Output is correct
12 Correct 268 ms 21808 KB Output is correct
13 Correct 235 ms 22468 KB Output is correct
14 Correct 235 ms 22196 KB Output is correct
15 Correct 290 ms 21772 KB Output is correct
16 Correct 184 ms 22592 KB Output is correct
17 Correct 271 ms 21896 KB Output is correct
18 Correct 259 ms 26124 KB Output is correct
19 Correct 241 ms 22060 KB Output is correct
20 Correct 264 ms 21796 KB Output is correct