oj.uz

Submission #522390

# Submission time Handle Problem Language Result Execution time Memory
522390 2022-02-04T18:31:04 Z N1NT3NDO Papričice (COCI20_papricice) C++14
110 / 110
 785 ms 24384 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();
    //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 4 ms 4992 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
35.0 / 35.0

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

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4992 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 Correct 6 ms 5068 KB Output is correct
7 Correct 6 ms 5040 KB Output is correct
8 Correct 5 ms 5036 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 6 ms 5068 KB Output is correct
11 Correct 556 ms 15940 KB Output is correct
12 Correct 704 ms 15864 KB Output is correct
13 Correct 251 ms 16216 KB Output is correct
14 Correct 376 ms 16032 KB Output is correct
15 Correct 659 ms 15940 KB Output is correct
16 Correct 151 ms 15632 KB Output is correct
17 Correct 467 ms 15980 KB Output is correct
18 Correct 785 ms 24384 KB Output is correct
19 Correct 425 ms 16136 KB Output is correct
20 Correct 585 ms 15904 KB Output is correct