oj.uz

답안 #329263

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
329263 2020-11-20T01:16:28 Z 534351 Papričice (COCI20_papricice) C++17
50 / 110
 1000 ms 36840 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]);
}
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

# 결과 실행 시간 메모리 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 11 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 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 11 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 11 ms 14700 KB Output is correct
7 Correct 12 ms 14700 KB Output is correct
8 Correct 11 ms 14700 KB Output is correct
9 Correct 13 ms 14700 KB Output is correct
10 Correct 12 ms 14700 KB Output is correct

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 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 11 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 11 ms 14700 KB Output is correct
7 Correct 12 ms 14700 KB Output is correct
8 Correct 11 ms 14700 KB Output is correct
9 Correct 13 ms 14700 KB Output is correct
10 Correct 12 ms 14700 KB Output is correct
11 Correct 330 ms 35948 KB Output is correct
12 Correct 379 ms 36716 KB Output is correct
13 Correct 274 ms 35748 KB Output is correct
14 Correct 299 ms 36204 KB Output is correct
15 Correct 356 ms 36716 KB Output is correct
16 Correct 244 ms 34408 KB Output is correct
17 Correct 297 ms 36076 KB Output is correct
18 Execution timed out 1086 ms 36840 KB Time limit exceeded
19 Halted 0 ms 0 KB -