oj.uz

Submission #314864

# Submission time Handle Problem Language Result Execution time Memory
314864 2020-10-21T14:23:37 Z model_code Papričice (COCI20_papricice) C++17
110 / 110
 278 ms 20088 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 10, INF = 1e9;

int n, sz[MAXN];
vector<int> e[MAXN];
set<int> A, B;

int calc_sz(int x, int p) {
    sz[x] = 1;
    for (auto y : e[x]) {
        if (y != p) sz[x] += calc_sz(y, x);
    }
    return sz[x];
}

vector<int> closest(const set<int>& S, int val) {
    vector<int> result;
    auto it = S.upper_bound(val);
    if (it != S.end()) result.push_back(*it);
    if (it != S.begin()) {
        --it;
        result.push_back(*it);
    }
    return result;
}

int balance(int a, int b, int c) {
    return max({a, b, c}) - min({a, b, c});
}

int solve(int x, int p) {
    int sol = INF;

    for (auto other_sz : closest(A, (n + sz[x]) / 2))
        sol = min(sol, balance(sz[x], other_sz - sz[x], n - other_sz));
    for (auto other_sz : closest(B, (n - sz[x]) / 2))
        sol = min(sol, balance(sz[x], other_sz, n - sz[x] - other_sz));

    A.insert(sz[x]);
    for (auto y : e[x]) {
        if (y != p) sol = min(sol, solve(y, x));
    }
    A.erase(sz[x]);
    B.insert(sz[x]);

    return sol;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }

    calc_sz(1, -1);

    int sol = solve(1, -1);
    cout << sol << '\n';

    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

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

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 5 ms 5120 KB Output is correct
7 Correct 5 ms 5120 KB Output is correct
8 Correct 5 ms 5120 KB Output is correct
9 Correct 5 ms 5120 KB Output is correct
10 Correct 5 ms 5120 KB Output is correct
11 Correct 269 ms 12604 KB Output is correct
12 Correct 278 ms 12240 KB Output is correct
13 Correct 223 ms 12872 KB Output is correct
14 Correct 245 ms 12536 KB Output is correct
15 Correct 273 ms 12284 KB Output is correct
16 Correct 184 ms 13068 KB Output is correct
17 Correct 241 ms 12280 KB Output is correct
18 Correct 265 ms 20088 KB Output is correct
19 Correct 246 ms 12536 KB Output is correct
20 Correct 253 ms 12280 KB Output is correct