oj.uz

Submission #876106

# Submission time Handle Problem Language Result Execution time Memory
876106 2023-11-21T09:09:41 Z cheat_when_I_was_young Papričice (COCI20_papricice) C++17
50 / 110
 223 ms 36740 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], res[NM];
vector<int> adj[NM];
set<int> a[NM];

void dfs_diameter(int u, int par, int depth, pair<int,int> &ans) {
    ans = max(ans, {depth, u});

    for (auto &v: adj[u]) if (v != par)
        dfs_diameter(v, u, depth + 1, ans);
}

pair<int,int> find_diameter() {
    pair<int,int> ans = {-1, -1};
    dfs_diameter(1, 1, 0, ans);

    int s = ans.second;
    ans = {-1, -1};
    dfs_diameter(s, s, 0, ans);

    return {s, ans.second};
}

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

    for (auto &v: adj[u])
        if (!sz[v]) {
            dfs(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];
        }

    auto k = a[u].upper_bound(sz[u]);
    int mi = INT_MAX;

    if (k != a[u].end() && mi > *k - sz[u]) {
        mi = *k - sz[u];
        res[u] = *k / 2;
    }

    if (k != a[u].begin()) {
        --k;
        if (mi > sz[u] - *k) {
            mi = sz[u] - *k;
            res[u] = *k / 2;
        }
    }

    a[u].insert(2 * sz[u]);
}

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

    dfs(s);
    
    int ans = INT_MAX;

    for (int i = 1; i <= n; ++i) {
        vector<int> b = {res[i], sz[i] - res[i], n - sz[i]};
        sort(b.begin(), b.end());
        ans = min(ans, b[2] - b[0]);
    }

    return ans;
}

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);
    }

    auto [s, t] = find_diameter();

    cout << min(ac(s), ac(t));
}

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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15708 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 4 ms 15708 KB Output is correct
4 Correct 3 ms 15708 KB Output is correct
5 Correct 3 ms 15764 KB Output is correct
6 Correct 5 ms 15964 KB Output is correct
7 Correct 5 ms 15964 KB Output is correct
8 Correct 4 ms 15964 KB Output is correct
9 Correct 4 ms 15964 KB Output is correct
10 Correct 4 ms 15836 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15708 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 4 ms 15708 KB Output is correct
4 Correct 3 ms 15708 KB Output is correct
5 Correct 3 ms 15764 KB Output is correct
6 Correct 5 ms 15964 KB Output is correct
7 Correct 5 ms 15964 KB Output is correct
8 Correct 4 ms 15964 KB Output is correct
9 Correct 4 ms 15964 KB Output is correct
10 Correct 4 ms 15836 KB Output is correct
11 Correct 212 ms 36020 KB Output is correct
12 Correct 223 ms 36740 KB Output is correct
13 Correct 200 ms 35288 KB Output is correct
14 Correct 194 ms 35644 KB Output is correct
15 Correct 221 ms 36688 KB Output is correct
16 Incorrect 170 ms 34048 KB Output isn't correct
17 Halted 0 ms 0 KB -