제출 #1352789

#제출 시각아이디문제언어결과실행 시간메모리
1352789daotuankhoiTorrent (COI16_torrent)C++20
100 / 100
175 ms23820 KiB
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

template <class T> bool ckmax(T &a, T b) { return a < b ? (a = b, true) : false; }
template <class T> bool ckmin(T &a, T b) { return a > b ? (a = b, true) : false; }

const int MAXN = 3e5 + 5;
int n, a, b;
vector<int> g[MAXN];

vector<int> path;

bool dfs(int u, int p) {
    path.emplace_back(u);
    if (u == b) return 1;
    for (int v : g[u]) {
        if (v != p && dfs(v, u)) return 1;
    }
    path.pop_back();
    return 0;
}

ll calc(int u, int p, int ban) {
    ll ans = 0;
    vector<ll> s;
    for (int v : g[u]) {
        if (v != p && v != ban) {
            ll val = calc(v, u, ban);
            s.emplace_back(val);
        }
    }
    sort(s.rbegin(), s.rend());
    int cnt = 1;
    for (ll val : s) {
        ckmax(ans, val + cnt);
        cnt++;
    }
    return ans;
}

pair<ll, ll> cost(int x, int y) {
    return {calc(a, 0, path[y]), calc(b, 0, path[x])};
}

int main() {
    #define NAME "test"
    if (fopen(NAME".inp", "r")) {
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> a >> b;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    dfs(a, 0);
    if (path.size() == 2) {
        auto [x, y] = cost(0, 1);
        cout << max(x, y) << '\n';
        return 0;
    }
    int l = 0, r = path.size() - 2, ans = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        auto [x, y] = cost(mid, mid + 1);
        if (x <= y) {
            l = mid + 1, ans = mid;
        } else r = mid - 1;
    }

    auto [x, y] = cost(ans, ans + 1);
    ll res = max(x, y);
    if (ans + 2 < (int)path.size()) {
            tie(x, y) = cost(ans + 1, ans + 2);
            ckmin(res, max(x, y));
    }
    cout << res << '\n';
    return 0;
}

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

torrent.cpp: In function 'int main()':
torrent.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen(NAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen(NAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...