제출 #876106

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
876106		cheat_when_I_was_young	Papričice (COCI20_papricice)	C++17	50 / 110	223 ms	36740 KiB

papricice

#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() {
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 15
• Subtask 2: 35 / 35
• Subtask 3: 0 / 60