제출 #1290876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290876		uranium235	Torrent (COI16_torrent)	C++17	100 / 100	207 ms	24472 KiB

torrent

#include <bits/stdc++.h>
using namespace std;

template <class a, class b> ostream& operator<<(ostream &l, const pair<a, b> &r) {
    l << "(" << r.first << ", " << r.second << ")" << endl;
}

template <class t> ostream& operator<<(ostream &l, const vector<t> &r) {
    l << "{";
    for (int i = 0; i + 1 < r.size(); i++) l << r[i] << ", ";
    if (!r.empty()) l << r.back();
    l << "}";
    return l;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, a, b;
    cin >> n >> a >> b;
    a--, b--;

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

    vector<int> par(n);
    auto marks = [&](int v, int p, auto &&self) -> void {
        par[v] = p;
        for (int i : adj[v]) {
            if (i != p) {
                self(i, v, self);
            }
        }
    };
    marks(a, -1, marks);
    vector<int> path;
    int ptr = b;
    do {
        path.push_back(ptr);
        ptr = par[ptr];
    } while (ptr != a);
    path.push_back(a);

    vector<int> dp(n, 1e6);
    int banned = -1;
    auto dfs = [&](int v, int p, auto &&self) -> void {
        for (int i : adj[v]) {
            if (i != p && i != banned) {
                self(i, v, self);
            }
        }

        vector<int> unmarks;
        unmarks.reserve(adj[v].size() - 1);
        for (int i : adj[v]) {
            if (i != p && i != banned) {
                unmarks.push_back(dp[i]);
            }
        }
        sort(unmarks.begin(), unmarks.end());
        reverse(unmarks.begin(), unmarks.end());
        int time = 0;
        // greedily assign longest child times to earliest copy
        for (int i = 0; i < unmarks.size(); i++) {
            time = max(time, i + 1 + unmarks[i]);
        }
        dp[v] = time;
    };

    auto eval = [&](int x) -> pair<int, int> {
        banned = path[x];
        dfs(b, -1, dfs);
        int bCost = dp[b];
        banned = path[x - 1];
        dfs(a, -1, dfs);
        int aCost = dp[a];

        // cout << "eval " << x << " " << aCost << " " << bCost << endl;
        return {aCost, bCost};
    };
    

    int lo = 0, hi = path.size() - 1;
    // last one s.t. a part is strictly greater than b part
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;
        pair<int, int> costs = eval(mid);
        if (costs.first > costs.second) {
            lo = mid;
        } else {
            hi = mid - 1;
        }
    }

    int ans = 1e6;
    if (lo > 0) {
        pair<int, int> cur = eval(lo);
        ans = max(cur.first, cur.second);
    }


    if (lo < path.size() - 1) {
        pair<int, int> cur = eval(lo + 1);
        ans = min(ans, max(cur.first, cur.second));
    }

    // cout << path << endl;
    // cout << lo << endl;
    cout << ans << '\n';;
}

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

torrent.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::pair<_T1, _T2>&)':
torrent.cpp:6:1: warning: no return statement in function returning non-void [-Wreturn-type]
    6 | }
      | ^

• Subtask 1: 31 / 31
• Subtask 2: 69 / 69