oj.uz

Submission #1101268

# Submission time Handle Problem Language Result Execution time Memory
1101268 2024-10-16T02:04:56 Z huantran Papričice (COCI20_papricice) C++17
110 / 110
 128 ms 24908 KB 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string.h>
#include <vector>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <numeric>
#include <random>
#include <chrono>
#include <fstream>
#include <stack>
#include <cmath>
#define bit(x, i) (((x) >> (i)) & 1LL)
#define rand rd
#define PI acos(-1)

using namespace std;
typedef long long int ll;
const int maxn = 2e5 + 5;
const ll mod = 1e9 + 7;
const int inf = 1e9;
const ll base = 1e5 + 7;
using pll = pair<ll, ll>;

const string NAME = "LOCO";
const int NTEST = 100;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

ll Rand(ll l, ll r) {
    return l + rd() % (r - l + 1);
}

int n, cnt = 0;
vector<int> adj[maxn];
int sz[maxn], tin[maxn], tout[maxn];
set<int> is_anc, is_not_anc;

void dfs_sz(int u, int p) {
    tin[u] = ++cnt;
    sz[u] = 1;

    for (auto j : adj[u]) {
        if (j == p)
            continue;
        dfs_sz(j, u);
        sz[u] += sz[j];
    }

    tout[u] = cnt;
}

vector<int> find_pos(set<int> &s, int val) {
    vector<int> res;
    auto it = s.upper_bound(val);
    if (it != s.end())
        res.push_back(*it);
    if (it != s.begin()) {
        --it;
        res.push_back(*it);
    }

    return res;
}

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

int go(int u, int p) {
    is_anc.insert(sz[u]);

    int res = inf;

    for (auto j : find_pos(is_anc, (n + sz[u]) / 2)) {
        res = min(res, calc(sz[u], j - sz[u], n - j));
    }

    for (auto j : find_pos(is_not_anc, (n - sz[u]) / 2)) {
        res = min(res, calc(sz[u], j, n - j - sz[u]));
    }

    for (auto j : adj[u]) {
        if (j == p)
            continue;
        res = min(go(j, u), res);
    }

    is_anc.erase(sz[u]);
    is_not_anc.insert(sz[u]);

    return res;
}

int main() {    
    // #ifndef ONLINE_JUDGE
    //     freopen("TASK.inp", "r", stdin);
    //     freopen("TASK.out", "w", stdout);
    // #endif // ONLINE_JUDGE

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

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

    dfs_sz(1, 1);
    cout << go(1, 1);
}

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

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

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7252 KB Output is correct
2 Correct 2 ms 7252 KB Output is correct
3 Correct 2 ms 7252 KB Output is correct
4 Correct 2 ms 7336 KB Output is correct
5 Correct 2 ms 7252 KB Output is correct
6 Correct 2 ms 7252 KB Output is correct
7 Correct 3 ms 7252 KB Output is correct
8 Correct 3 ms 7252 KB Output is correct
9 Correct 3 ms 7252 KB Output is correct
10 Correct 2 ms 7252 KB Output is correct
11 Correct 82 ms 16204 KB Output is correct
12 Correct 103 ms 16352 KB Output is correct
13 Correct 79 ms 16800 KB Output is correct
14 Correct 85 ms 16584 KB Output is correct
15 Correct 91 ms 16216 KB Output is correct
16 Correct 62 ms 16072 KB Output is correct
17 Correct 96 ms 16480 KB Output is correct
18 Correct 128 ms 24908 KB Output is correct
19 Correct 83 ms 16460 KB Output is correct
20 Correct 122 ms 16460 KB Output is correct