oj.uz

Submission #329266

# Submission time Handle Problem Language Result Execution time Memory
329266 2020-11-20T01:55:43 Z 534351 Papričice (COCI20_papricice) C++17
110 / 110
 293 ms 33388 KB 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>

using namespace std;
// using namespace __gnu_pbds;

// template<class T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

const int MAXN = 200013;

int N;
vi edge[MAXN];
int parent[MAXN], subtree[MAXN];
set<int> sizes[MAXN];
int ans;
vi nums;

void dfs(int u, int p)
{
    subtree[u] = 1;
    for (int v : edge[u])
    {
        if (v == p) continue;
        parent[v] = u;
        dfs(v, u);
        subtree[u] += subtree[v];
    }
}

//case 0: they're in same subtree

int calc(int a, int b)
{
    int c = N - a - b;
    // cerr << "calc " << a << ' ' << b << endl;
    return max(a, max(b, c)) - min(a, min(b, c));
}
void solve(set<int> &a, set<int> &b)
{
    for (int x : a)
    {
        auto it = b.LB((N - x) / 2);
        if (it != b.end())
        {
            ckmin(ans, calc(x, *it));
        }
        if (it != b.begin())
        {
            ckmin(ans, calc(x, *prev(it)));
        }
    }
    return;
}
//case 1: they're in two separate subtrees
void solve1(int u)
{
    for (int v : edge[u])
    {
        if (v == parent[u]) continue;
        solve1(v);
    }
    for (int v : edge[u])
    {
        if (v == parent[u]) continue;
        if (SZ(sizes[v]) > SZ(sizes[u])) swap(sizes[u], sizes[v]);
        solve(sizes[u], sizes[v]);
        for (int x : sizes[v]) sizes[u].insert(x);
    }
    sizes[u].insert(subtree[u]);
    while(!sizes[u].empty() && *sizes[u].begin() * 3 + 2 * ans <= N) sizes[u].erase(sizes[u].begin());
    while(!sizes[u].empty() && *prev(sizes[u].end()) * 3 - 2 * ans >= N) sizes[u].erase(prev(sizes[u].end()));
}
void solve2(int u)
{
    nums.PB(subtree[u]);
    for (int v : edge[u])
    {
        if (v == parent[u]) continue;
        solve2(v);
    }
    nums.pop_back();
    int sz = (N + subtree[u]) / 2;
    auto it = LB(ALL(nums), sz, greater<int>());
    if (it != nums.end())
    {
        ckmin(ans, calc(subtree[u], *it - subtree[u]));
    }
    if (it != nums.begin())
    {
        ckmin(ans, calc(subtree[u], *prev(it) - subtree[u]));
    }
    return;
    //now solve: one cut is subtree[u], the other cut is smth before
}

int32_t main()
{
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(4);
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N;
    FOR(i, 0, N - 1)
    {
        int u, v;
        cin >> u >> v; u--; v--;
        edge[u].PB(v);
        edge[v].PB(u);
    }
    parent[0] = N;
    dfs(0, N);
    ans = N;
    solve2(0);
    solve1(0);
    cout << ans << '\n';
    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

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

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Correct 10 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 10 ms 14572 KB Output is correct
7 Correct 10 ms 14572 KB Output is correct
8 Correct 10 ms 14572 KB Output is correct
9 Correct 10 ms 14572 KB Output is correct
10 Correct 11 ms 14572 KB Output is correct
11 Correct 272 ms 22636 KB Output is correct
12 Correct 293 ms 22380 KB Output is correct
13 Correct 279 ms 33388 KB Output is correct
14 Correct 252 ms 22892 KB Output is correct
15 Correct 283 ms 22372 KB Output is correct
16 Correct 237 ms 32616 KB Output is correct
17 Correct 239 ms 22636 KB Output is correct
18 Correct 216 ms 29672 KB Output is correct
19 Correct 252 ms 25196 KB Output is correct
20 Correct 245 ms 25068 KB Output is correct