oj.uz

Submission #1090719

# Submission time Handle Problem Language Result Execution time Memory
1090719 2024-09-18T15:54:24 Z kh0i Papričice (COCI20_papricice) C++17
110 / 110
 136 ms 29264 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

using ll = long long;
using pii = pair<int, int>;

#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    assert(l <= r);
    return uniform_int_distribution<ll> (l, r)(rng);
}

const int N = 2e5 + 3;

int n, sz[N];
vector<int> g[N];

void dfs(int u, int pre = -1){
    sz[u] = 1;
    for(int v : g[u]){
        if(v == pre)
            continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

int res = INT_MAX;
multiset<ll> out, anc;

void calc(int u, int pre = -1){
    auto it = out.lower_bound((n - sz[u]) / 2);
    if(it != out.end()){
        int x = *it, y = n - *it - sz[u];
        res = min(res, max({x, y, sz[u]}) - min({x, y, sz[u]}));
    }
    if(it != out.begin()){
        --it;
        int x = *it, y = n - *it - sz[u];
        res = min(res, max({x, y, sz[u]}) - min({x, y, sz[u]}));
    }

    it = anc.lower_bound((n + sz[u]) / 2);
    if(it != anc.end()){
        int x = *it - sz[u], y = n - *it;
        res = min(res, max({x, y, sz[u]}) - min({x, y, sz[u]}));
    }
    if(it != anc.begin()){
        --it;
        int x = *it - sz[u], y = n - *it;
        res = min(res, max({x, y, sz[u]}) - min({x, y, sz[u]}));
    }

    // debug(u, pre, out, anc, res);

    if(u != 1)
        anc.insert(sz[u]);

    for(int v : g[u]){
        if(v == pre)
            continue;
        calc(v, u);
    }

    if(u != 1){
        anc.erase(anc.find(sz[u]));
        out.insert(sz[u]);
    }
}

void solve(){
    cin >> n;
    for(int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1);
    calc(1);

    cout << res;
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    #define task "troll"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int test = 1;
//    cin >> test;
    for(int i = 1; i <= test; ++i){
//        cout << "Case #" << i << ": ";
        solve();
    }
    #ifdef LOCAL
        cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    #endif
    return 0;
}

Compilation message

papricice.cpp: In function 'int32_t main()':
papricice.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
papricice.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 5164 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4952 KB Output is correct
6 Correct 2 ms 5208 KB Output is correct
7 Correct 3 ms 5208 KB Output is correct
8 Correct 2 ms 5208 KB Output is correct
9 Correct 2 ms 5244 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 5164 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4952 KB Output is correct
6 Correct 2 ms 5208 KB Output is correct
7 Correct 3 ms 5208 KB Output is correct
8 Correct 2 ms 5208 KB Output is correct
9 Correct 2 ms 5244 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 115 ms 23972 KB Output is correct
12 Correct 133 ms 24148 KB Output is correct
13 Correct 97 ms 24516 KB Output is correct
14 Correct 121 ms 24356 KB Output is correct
15 Correct 115 ms 24068 KB Output is correct
16 Correct 95 ms 23900 KB Output is correct
17 Correct 130 ms 24144 KB Output is correct
18 Correct 136 ms 29264 KB Output is correct
19 Correct 105 ms 24148 KB Output is correct
20 Correct 132 ms 24148 KB Output is correct