oj.uz

Submission #1045025

# Submission time Handle Problem Language Result Execution time Memory
1045025 2024-08-05T15:42:09 Z Beerus13 Papričice (COCI20_papricice) C++14
110 / 110
 137 ms 30292 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 5;
const int inf = 1e9;

bool minimize(int &a, int b) {
    if(a <= b) return true;
    a = b;
    return false;
}

int n, sz[N], ans = inf;
vector<int> g[N];
multiset<int> anc, oth;

vector<int> opt(int x, multiset<int> &sett) {
    auto it = sett.lower_bound(x);
    vector<int> v;
    v.push_back(*it);
    --it;
    v.push_back(*it);
    return v;
}

int cost(int a, int b, int c) {
    return max({a, b, c}) - min({a, b, c});
}

void dfs_size(int u, int p = 0) {
    sz[u] = 1;
    for(int v : g[u]) if(v != p) {
        dfs_size(v, u);
        sz[u] += sz[v];
    }
}

void dfs(int u, int p = 0) {
    for(int x : opt(n + sz[u] >> 1, anc)) {
        minimize(ans, cost(sz[u], n - x, x - sz[u]));
    }
    for(int x : opt(n - sz[u] >> 1, oth)) {
        minimize(ans, cost(sz[u], n - sz[u] - x, x));
    }
    anc.insert(sz[u]);
    for(int v : g[u]) if(v != p) dfs(v, u);
    anc.erase(anc.find(sz[u]));
    oth.insert(sz[u]);
}

void solve() {
    cin >> n;
    for(int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    anc.insert(-inf); anc.insert(inf);
    oth.insert(-inf); oth.insert(inf);
    dfs_size(1);
    dfs(1);
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int test = 1;
    // cin >> test;
    while(test--) solve();
    return 0;
}

Compilation message

papricice.cpp: In function 'void dfs(int, int)':
papricice.cpp:39:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     for(int x : opt(n + sz[u] >> 1, anc)) {
      |                     ~~^~~~~~~
papricice.cpp:42:23: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   42 |     for(int x : opt(n - sz[u] >> 1, oth)) {
      |                     ~~^~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

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

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 1 ms 5156 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 2 ms 5176 KB Output is correct
10 Correct 2 ms 5244 KB Output is correct
11 Correct 135 ms 24096 KB Output is correct
12 Correct 127 ms 24088 KB Output is correct
13 Correct 93 ms 24404 KB Output is correct
14 Correct 137 ms 24148 KB Output is correct
15 Correct 131 ms 24392 KB Output is correct
16 Correct 90 ms 24016 KB Output is correct
17 Correct 103 ms 24148 KB Output is correct
18 Correct 131 ms 30292 KB Output is correct
19 Correct 102 ms 24260 KB Output is correct
20 Correct 121 ms 24096 KB Output is correct