oj.uz

Submission #522391

# Submission time Handle Problem Language Result Execution time Memory
522391 2022-02-04T18:33:08 Z N1NT3NDO Papričice (COCI20_papricice) C++14
110 / 110
 770 ms 21740 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define sd second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("-Ofast")
//#pragma GCC target("avx2")
typedef long long ll;

//using namespace __gnu_pbds;
using namespace std;

//typedef tree<int, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = (int)2e5 + 500;
int n, sz[N], ans = 1e9, used[N];
vector<int> g[N];
set<int> out, in;
vector<int> vec;

void sizes(int v, int p)
{
    sz[v] = 1;
    for(auto u : g[v])
    {
        if (u == p || used[u]) continue;
        sizes(u, v);
        sz[v] += sz[u];
    }
}

int centoid(int v, int p, int siz)
{
    for(auto u : g[v])
    {
        if (u == p || used[u] || sz[u] < siz / 2) continue;
        return centoid(u, v, siz);
    }
    return v;
}

void dfs(int v, int p)
{
    vec.pb(sz[v]);
    if (sz(in) > 0)
    {
        auto it = in.lower_bound((n + sz[v]) / 2);
        if (it != in.end())
        {
            int cur = *it;
            ans = min(ans, max({sz[v], cur - sz[v], n - cur}) - min({sz[v], cur - sz[v], n - cur}));
        }

        if (it != in.begin())
        {
            it--;
            int cur = *it;
            ans = min(ans, max({sz[v], cur - sz[v], n - cur}) - min({sz[v], cur - sz[v], n - cur}));
        }
    }

    in.insert(sz[v]);

    if (sz(out) > 0)
    {
        auto it = out.lower_bound((n - sz[v]) / 2);
        if (it != out.end())
        {
            int cur = *it;
            ans = min(ans, max({sz[v], cur, n - cur - sz[v]}) - min({sz[v], cur, n - cur - sz[v]}));
        }

        if (it != out.begin())
        {
            it--;
            int cur = *it;
            ans = min(ans, max({sz[v], cur, n - cur - sz[v]}) - min({sz[v], cur, n - cur - sz[v]}));
        }
    }

    for(auto u : g[v])
    {
        if (u == p || used[u]) continue;
        dfs(u, v);
    }
}

void solve(int v)
{
    sizes(v, v);
    v = centoid(v, v, sz[v]);
    sizes(v, v);
    out.clear();
    for(const auto u : g[v])
    {
        if (used[u]) continue;
        vec.clear();
        in.clear();
        in.insert(sz[v]);
        dfs(u, v);
        for(const auto val : vec)
          out.insert(val);
    }

    used[v] = 1;
    for(const auto u : g[v])
        if (!used[u])
          solve(u);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    solve(1);

    cout << ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 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 2 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 5 ms 5068 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 6 ms 5068 KB Output is correct
10 Correct 5 ms 5068 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 5 ms 5068 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 6 ms 5068 KB Output is correct
10 Correct 5 ms 5068 KB Output is correct
11 Correct 498 ms 13432 KB Output is correct
12 Correct 643 ms 13404 KB Output is correct
13 Correct 248 ms 13860 KB Output is correct
14 Correct 354 ms 13644 KB Output is correct
15 Correct 621 ms 13448 KB Output is correct
16 Correct 125 ms 13888 KB Output is correct
17 Correct 464 ms 13564 KB Output is correct
18 Correct 770 ms 21740 KB Output is correct
19 Correct 449 ms 13644 KB Output is correct
20 Correct 576 ms 13376 KB Output is correct