Submission #712373

#	Time	Username	Problem	Language	Result	Execution time	Memory
712373		stevancv	Torrent (COI16_torrent)	C++14	0 / 100	653 ms	25624 KiB

torrent

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 3e5 + 2;
const int inf = 1e9;
vector<pair<int, int>> g[N];
int par[N];
void Dfs(int s, int e) {
    for (auto u : g[s]) {
        if (u.first == e) continue;
        par[u.first] = u.second;
        Dfs(u.first, s);
    }
}
int Dfs1(int s, int e, int c) {
    vector<int> all;
    for (auto u : g[s]) {
        if (u.first == e || u.second == c) continue;
        all.push_back(Dfs1(u.first, s, c));
    }
    sort(all.rbegin(), all.rend());
    int o = 0;
    for (int i = 0; i < all.size(); i++) {
        smax(o, all[i] + i + 1);
    }
    return o;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, a, b;
    cin >> n >> a >> b;
    vector<int> u(n - 1), v(n - 1);
    for (int i = 0; i < n - 1; i++) {
        cin >> u[i] >> v[i];
        g[u[i]].push_back({v[i], i});
        g[v[i]].push_back({u[i], i});
        par[i] = -1;
    }
    Dfs(a, 0);
    for (int i = 0; i < n - 1; i++) {
        if (par[v[i]] != i) swap(u[i], v[i]);
    }
    vector<int> p;
    int x = b;
    while (x != a) {
        p.push_back(par[x]);
        x = u[par[x]];
    }
    int sz = p.size();
    if (a == b) {
        cout << Dfs1(a, 0, -1) << en;
        return 0;
    }
    int l = 0, r = sz - 2, gde = sz - 1;
    while (l <= r) {
        int mid = l + r >> 1;
        int c = p[mid]; int d = p[mid + 1];
        if (max(Dfs1(a, 0, c), Dfs1(b, 0, c)) >= max(Dfs1(a, 0, d), Dfs1(b, 0, d))) {
            l = mid + 1;
        }
        else {
            gde = mid;
            r = mid - 1;
        }
    }
    cout << max(Dfs1(a, 0, p[gde]), Dfs1(b, 0, p[gde])) << en;
    return 0;
}

Compilation message (stderr)

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

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