Submission #846684

#	Time	Username	Problem	Language	Result	Execution time	Memory
846684		vjudge1	Torrent (COI16_torrent)	C++17	69 / 100	300 ms	25292 KiB

torrent

#include <bits/stdc++.h>

using namespace std;
#define task "code"

const int ar = 3e5 + 1;
const int inf = 1e9 + 5;

int n, a, b, u, v, dp[ar], res = inf;
vector<int> adj[ar];
vector< pair<int, int> > vec;

bool c = false;
void find_dfs(int u, int p) {
    if (u == b) {
        c = true;
        return;
    }
    for (int v : adj[u]) if (v != p) {
        find_dfs(v, u);
        if (c == true) {
            vec.push_back({u, v});
            return ;
        }
    }
}

int dfs (int u, int p, int x) {
    vector<int> vc;
    for (int v : adj[u])
        if (v != p && v != x)
            vc.push_back(dfs(v, u, x));

    int ans = 0;
    sort (vc.begin(), vc.end(), greater<int>());
    for (int i = 0; i < vc.size(); ++ i)
        ans = max(ans, vc[i] + i + 1);

//    cout << u << ' ' << p << ' ' << ans << '\n';
//    cout << "vc: ";
//    for (int x : vc) cout << x << ' '; cout << '\n';
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> a >> b;
    for (int i = 1; i < n; ++ i) {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    if (a == b) return cout << dfs(a, 0, 0), 0;
    find_dfs(a, 0);

        int l = 0, r = vec.size() - 1;
        while (l <= r) {
            int m = l + r >> 1;
    //        cout << vec[m].first << ' ' << vec[m].second << '\n';
            int valA = dfs(a, 0, vec[m].second), valB = dfs(b, 0, vec[m].first);
            res = min(res, max(valA, valB));
            if (valA >= valB) r = m - 1;
            else l = m + 1;
        }

    cout << res;

    return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'int dfs(int, int, int)':
torrent.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 0; i < vc.size(); ++ i)
      |                     ~~^~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:61:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |             int m = l + r >> 1;
      |                     ~~^~~

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