oj.uz

Submission #522388

# Submission time Handle Problem Language Result Execution time Memory
522388 2022-02-04T18:29:03 Z N1NT3NDO Papričice (COCI20_papricice) C++14
15 / 110
 7 ms 5168 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];
multiset<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();
    out.insert(sz[v]);
    for(auto u : g[v])
    {
        if (used[u]) continue;
        vec.clear();
        in.clear();
        in.insert(sz[v]);
        dfs(u, v);
        for(auto val : vec)
          out.insert(val);
    }

    used[v] = 1;
    for(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 3 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 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Incorrect 7 ms 5168 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Incorrect 7 ms 5168 KB Output isn't correct
7 Halted 0 ms 0 KB -