oj.uz

Submission #931094

# Submission time Handle Problem Language Result Execution time Memory
931094 2024-02-21T08:27:54 Z Whisper Papričice (COCI20_papricice) C++17
110 / 110
 170 ms 24320 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for ( int i = a ; i <= b ; i++ )
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)
#define pii pair<int , int>
#define Lg(x) 31 - __builtin_clz(x)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int MAX = 2e5 + 5;
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }

int numNode;
vector<int> adj[MAX];
int sz[MAX];
void reSubsize(int u, int p = -1){
    sz[u] = 1;
    for (auto&v : adj[u]) if(v ^ p){
        reSubsize(v, u);
        sz[u] += sz[v];
    }
}
int optimize(int a, int b, int c){
    return max({a, b, c}) - min({a, b, c});
}
int ans = INF;
set<int> a, b;
vector<int> compute(set<int>&x, int v){
    auto it = x.lower_bound(v);
    vector<int> res;
    if (it != x.end()) res.push_back(*it);
    if (it != x.begin()) res.push_back(*(--it));
    return res;
}
void dfs(int u, int p){
    for (int szA : compute(a, (numNode + sz[u]) / 2)){
        minimize(ans, optimize(sz[u], szA - sz[u], numNode - szA));
    }
    for (int szB : compute(b, (numNode - sz[u]) / 2)){
        minimize(ans, optimize(sz[u], szB, numNode - sz[u] - szB));
    }
    a.insert(sz[u]);
    for (auto&v : adj[u]) if(v ^ p){
        dfs(v, u);
    }
    a.erase(sz[u]);
    b.insert(sz[u]);
}
void Whisper(){
    cin >> numNode;
    for (int i = 1; i < numNode; ++i){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    reSubsize(1);
    dfs(1, 0);
    cout << ans;
}


signed main(){
    setupIO();
    int Test = 1;
//    cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

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

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6476 KB Output is correct
4 Correct 2 ms 6488 KB Output is correct
5 Correct 3 ms 6492 KB Output is correct
6 Correct 3 ms 6488 KB Output is correct
7 Correct 3 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 104 ms 16636 KB Output is correct
12 Correct 132 ms 16464 KB Output is correct
13 Correct 96 ms 17072 KB Output is correct
14 Correct 96 ms 16716 KB Output is correct
15 Correct 154 ms 16496 KB Output is correct
16 Correct 68 ms 16196 KB Output is correct
17 Correct 105 ms 16684 KB Output is correct
18 Correct 170 ms 24320 KB Output is correct
19 Correct 100 ms 16932 KB Output is correct
20 Correct 112 ms 16464 KB Output is correct