Submission #286857

#	Time	Username	Problem	Language	Result	Execution time	Memory
286857		two_sides	Torrent (COI16_torrent)	C++17	100 / 100	472 ms	28916 KiB

torrent

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

#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

const int N = 300005;

vector <int> g[N];
vector <int> cur, path;
int n, a, b, dp[N];

void dfs1(int u, int p) {
    cur.eb(u);
    if (u == b) path = cur;
    for (int v : g[u])
        if (v != p) dfs1(v, u);
    cur.pop_back();
}

void dfs2(int u, int p, int exc) {
    dp[u] = 0;
    if (u == exc) return;
    for (int v : g[u])
        if (v != p && v != exc)
            dfs2(v, u, exc);
    cur.clear();
    for (int v : g[u])
        if (v != p && v != exc)
            cur.eb(dp[v]);
    sort(rall(cur));
    for (int i = 0; i < cur.size(); i++)
        dp[u] = max(dp[u], cur[i] + i + 1);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> a >> b;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].eb(v); g[v].eb(u);
    }
    dfs1(a, 0); dfs2(a, 0, 0);
    int res = dp[a];
    int lo = 0, hi = path.size() - 2;
    while (lo <= hi) {
        int mi = (lo + hi) / 2;
        dfs2(a, 0, path[mi + 1]);
        dfs2(b, 0, path[mi]);
        res = min(res, max(dp[a], dp[b]));
        if (dp[a] < dp[b]) lo = mi + 1;
        else hi = mi - 1;
    }
    cout << res << '\n';
}

Compilation message (stderr)

torrent.cpp: In function 'void dfs2(int, int, int)':
torrent.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0; i < cur.size(); i++)
      |                     ~~^~~~~~~~~~~~

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