oj.uz

Submission #955496

# Submission time Handle Problem Language Result Execution time Memory
955496 2024-03-30T15:24:39 Z manhlinh1501 Papričice (COCI20_papricice) C++17
110 / 110
 216 ms 28996 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int oo = 1e9;
#define sz(a) (int)a.size()
#define eb emplace_back
using pii = pair<int, int>;
int n;

namespace arcv {
    int n;
    vector<int> adj[N];
    int par[N];
    int sz[N];
    int st[N];
    int en[N];
    int tour[N];
    int ans = oo;
    int times = 0;
    multiset<int> S;

    void calc_sz(int u, int p) {
        par[u] = p;
        sz[u] = 1;

        for(int v : adj[u]) {
            if(v == p)
                continue;

            calc_sz(v, u);
            sz[u] += sz[v];
        }
    }

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

    void DFS1(int u, int p) {
        auto it = S.lower_bound((n - sz[u]) / 2);

        if(it != S.end())
            ans = min(ans, get(sz[u], *it, n - sz[u] - (*it)));

        if(it != S.begin())
            --it;

        if(it != S.end())
            ans = min(ans, get(sz[u], *it, n - sz[u] - (*it)));

        for(int v : adj[u]) {
            if(v == p)
                continue;

            DFS1(v, u);
        }

        S.emplace(sz[u]);
        en[u] = times;
    }

    void DFS2(int u, int p) {
        auto it = S.lower_bound((n + sz[u]) / 2);

        if(it != S.end())
            ans = min(ans, get((*it) - sz[u], sz[u], n - (*it)));

        if(it != S.begin())
            --it;

        if(it != S.end())
            ans = min(ans, get((*it) - sz[u], sz[u], n - (*it)));

        S.emplace(sz[u]);

        for(int v : adj[u]) {
            if(v == p)
                continue;

            DFS2(v, u);
        }

        S.erase(S.find(sz[u]));
    }

    void solution() {
        cin >> n;

        for(int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v;
            adj[u].eb(v);
            adj[v].eb(u);
        }

        calc_sz(1, 0);
        DFS1(1, 0);
        S.clear();
        DFS2(1, 0);

        cout << ans;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    arcv::solution();
}

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8792 KB Output is correct
2 Correct 3 ms 8792 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 3 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 3 ms 9052 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 4 ms 9048 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8792 KB Output is correct
2 Correct 3 ms 8792 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 3 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 3 ms 9052 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 4 ms 9048 KB Output is correct
11 Correct 155 ms 24660 KB Output is correct
12 Correct 195 ms 25068 KB Output is correct
13 Correct 148 ms 25392 KB Output is correct
14 Correct 216 ms 24952 KB Output is correct
15 Correct 190 ms 24792 KB Output is correct
16 Correct 117 ms 25292 KB Output is correct
17 Correct 184 ms 24736 KB Output is correct
18 Correct 175 ms 28996 KB Output is correct
19 Correct 157 ms 27212 KB Output is correct
20 Correct 164 ms 26960 KB Output is correct