oj.uz

Submission #876317

# Submission time Handle Problem Language Result Execution time Memory
876317 2023-11-21T14:32:14 Z cheat_when_I_was_young Papričice (COCI20_papricice) C++17
0 / 110
 4 ms 15196 KB 
#include "bits/stdc++.h"
using namespace std;
void open_file(const string &file_name) {
    if (fopen((file_name + ".inp").c_str(), "r")) {
        freopen((file_name + ".inp").c_str(), "r", stdin);
        freopen((file_name + ".out").c_str(), "w", stdout);
    }
}
void init();
void solve();
bool multitest();
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    clock_t TIME = clock();
    init();
    int TEST = 1;
    if (multitest()) cin >> TEST;
    while (TEST--) solve();
    cerr << "\nUsed: " << clock() - TIME << " ms\n\n";
}

bool multitest() {
    return 0;
}

const int NM = 2e5 + 5;

int n, sz[NM], ans = INT_MAX;
vector<int> adj[NM];
set<int> a[NM], b;

int C(set<int> &m, int x) {
    auto k = m.lower_bound(x);
    int mi = INT_MAX, res;

    if (k != m.end() && mi > abs(x - *k)) {
        mi = abs(x - *k);
        res = *k;
    }

    if (k != m.begin()) {
        --k;
        if (mi > abs(x - *k)) {
            mi = abs(x - *k);
            res = *k;
        }
    }

    return res;
}

int D(int x, int y, int z) {
    return max(max(x, y), z) - min(min(x, y), z);
}

void dfs(int u) {
    sz[u] = 1;

    if (b.size()) {
        int tmp = C(b, (n - sz[u]) / 2);
        ans = min(ans, D(sz[u], tmp, n - sz[u] - tmp));
    }

    for (auto &v: adj[u])
        if (!sz[v]) {
            dfs(v);

            b.insert(v);

            if (a[u].size() < a[v].size())
                swap(a[u], a[v]);

            for (auto &i: a[v])
                a[u].insert(i);

            sz[u] += sz[v];
        }

    a[u].insert(sz[u]);

    int tmp = C(a[u], sz[u] / 2);
    ans = min(ans, D(tmp, sz[u] - tmp, n - sz[u]));
}

void ac() {
    memset(sz, 0, sizeof(sz));
    b.clear();
    for (int i = 1; i <= n; ++i) a[i].clear();

    dfs(1);
}

void solve() {
    cin >> n;
    for (int x, y, i = 1; i < n; ++i) {
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    ac();
    for (int i = 1; i <= n; ++i)
        reverse(adj[i].begin(), adj[i].end());
    ac();

    cout << ans;
}

void init() {
}

Compilation message

papricice.cpp: In function 'void open_file(const string&)':
papricice.cpp:5:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 |         freopen((file_name + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
papricice.cpp:6:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 |         freopen((file_name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
papricice.cpp: In function 'int C(std::set<int>&, int)':
papricice.cpp:50:12: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |     return res;
      |            ^~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15196 KB Output is correct
2 Correct 3 ms 15196 KB Output is correct
3 Incorrect 3 ms 15196 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15196 KB Output is correct
2 Correct 3 ms 15196 KB Output is correct
3 Incorrect 3 ms 15196 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15196 KB Output is correct
2 Correct 3 ms 15196 KB Output is correct
3 Incorrect 3 ms 15196 KB Output isn't correct
4 Halted 0 ms 0 KB -