oj.uz

Submission #366484

# Submission time Handle Problem Language Result Execution time Memory
366484 2021-02-14T09:10:07 Z Vimmer Papričice (COCI20_papricice) C++14
110 / 110
 663 ms 21100 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("-O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-Ofast")

#define N 200500
#define NN 205000
#define PB push_back
#define endl '\n'
#define pri(x) cout << x << endl
#define _ << " " <<
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define M ll(1e9 + 7)
#define F first
#define S second

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef short int si;
typedef unsigned long long ull;

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

vector <int> g[N];

int ans = 1e9, siz[N], n;

multiset <int> str;
set <int> st;

void rec(int v, int p)
{
    siz[v] = 1;

    for (auto it : g[v])
    {
        if (it == p) continue;

        rec(it, v);

        siz[v] += siz[it];
    }
}
void dfs(int v, int p)
{
    int val = (n + siz[v]) / 2;

    int kol = 100;

    if (sz(str))
    {
        auto it = str.lower_bound(val);

        if (it == str.end()) it--;

        while (kol && sz(str))
        {
            int vt = (*it);

            int a1 = n - vt, a2 = vt - siz[v], a3 = siz[v];

            ans = min(ans, max(a1, max(a2, a3)) - min(a1, min(a2, a3)));

            kol--;

            if (it == str.begin())
                break;

            it--;
        }
    }

    kol = 100;

    if (sz(str))
    {
        auto it = str.lower_bound(val);

        if (it == str.end()) it--;

        while (kol && sz(str))
        {
            int vt = (*it);

            int a1 = n - vt, a2 = vt - siz[v], a3 = siz[v];

            ans = min(ans, max(a1, max(a2, a3)) - min(a1, min(a2, a3)));

            kol--;

            it++;

            if (it == str.end())
                break;
        }
    }

     if (sz(st))
        {
            int kol = 100;

            auto itr = st.lower_bound(val);

            if (itr == st.end()) itr--;

            while (kol && sz(st))
            {
                int vt = (*itr);

                int a1 = n - siz[v] - vt, a2 = siz[v], a3 = vt;

                int val = max(a1, max(a2, a3)) - min(a1, min(a2, a3));

                ans = min(ans, val);

                kol--;

                if (itr == st.begin())
                    break;

                itr--;
            }

            kol = 100;

            itr = st.lower_bound(val);

            while (kol)
            {
                int vt = (*itr);

                int a1 = n - siz[v] - vt, a2 = siz[v], a3 = vt;

                int val = max(a1, max(a2, a3)) - min(a1, min(a2, a3));

                ans = min(ans, val);

                kol--;

                itr++;

                if (itr == st.end())
                    break;
            }
        }

    str.insert(siz[v]);

    for (auto it : g[v])
    {
        if (it == p) continue;

        dfs(it, v);
    }

    str.erase(str.find(siz[v]));

    st.insert(siz[v]);
}

int main()
{
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("1.in", "r", stdin);

    cin >> n;

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

        cin >> x >> y;

        g[x].PB(y);

        g[y].PB(x);
    }

    rec(1, -1);

    dfs(1, -1);

    pri(ans);
}

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 6 ms 5228 KB Output is correct
7 Correct 6 ms 5100 KB Output is correct
8 Correct 5 ms 5100 KB Output is correct
9 Correct 5 ms 5100 KB Output is correct
10 Correct 6 ms 5100 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 6 ms 5228 KB Output is correct
7 Correct 6 ms 5100 KB Output is correct
8 Correct 5 ms 5100 KB Output is correct
9 Correct 5 ms 5100 KB Output is correct
10 Correct 6 ms 5100 KB Output is correct
11 Correct 363 ms 12332 KB Output is correct
12 Correct 525 ms 12396 KB Output is correct
13 Correct 314 ms 13044 KB Output is correct
14 Correct 337 ms 12652 KB Output is correct
15 Correct 428 ms 12268 KB Output is correct
16 Correct 154 ms 13160 KB Output is correct
17 Correct 371 ms 12396 KB Output is correct
18 Correct 643 ms 21100 KB Output is correct
19 Correct 350 ms 12660 KB Output is correct
20 Correct 663 ms 12460 KB Output is correct