oj.uz

Submission #955495

# Submission time Handle Problem Language Result Execution time Memory
955495 2024-03-30T15:17:13 Z manhlinh1501 Papričice (COCI20_papricice) C++17
50 / 110
 1000 ms 31488 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 DFS(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)));

        st[u] = ++times;
        tour[times] = u;

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

            DFS(v, u);
        }

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

    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);
        DFS(1, 0);

        for(int i = 1; i <= n; i++) {
            int x = i;

            while(x) {
                ans = min(ans, get(sz[i], sz[x] - sz[i], n - sz[x]));
                x = par[x];
            }
        }

        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 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8884 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct

Subtask #2
35.0 / 35.0

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

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8884 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 3 ms 9052 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 3 ms 8908 KB Output is correct
9 Correct 3 ms 9048 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct
11 Correct 193 ms 27240 KB Output is correct
12 Correct 225 ms 27220 KB Output is correct
13 Correct 132 ms 27732 KB Output is correct
14 Correct 153 ms 27412 KB Output is correct
15 Correct 174 ms 27288 KB Output is correct
16 Correct 107 ms 27088 KB Output is correct
17 Correct 139 ms 27216 KB Output is correct
18 Execution timed out 1063 ms 31488 KB Time limit exceeded
19 Halted 0 ms 0 KB -