oj.uz

Submission #937289

# Submission time Handle Problem Language Result Execution time Memory
937289 2024-03-03T18:46:32 Z spike1236 Torrent (COI16_torrent) C++14
100 / 100
 406 ms 29728 KB 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ll long long
#define ld long double
#define all(_v) _v.begin(), _v.end()
#define sz(_v) (int)_v.size()
#define pii pair <int, int>
#define pll pair <ll, ll>
#define veci vector <int>
#define vecll vector <ll>

// template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 rnd64(chrono::steady_clock::now().time_since_epoch().count());

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const double PI = 3.141592653589793;
const double eps = 1e-9;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;

const int MAXN = 3e5 + 10;
int n, A, B;
veci g[MAXN];
int par[MAXN], dp[MAXN];

void dfs(int v) {
    for (auto to : g[v]) {
        if (to == par[v]) continue;
        par[to] = v;
        dfs(to);
    }
}

int calc(int v, int p, int cx, int cy) {
    veci c;
    for (auto to : g[v]) {
        if (to == p) continue;
        if (v == cx && to == cy) continue;
        if (v == cy && to == cx) continue;
        calc(to, v, cx, cy);
        c.pb(dp[to]);
    }
    sort(all(c));
    reverse(all(c));
    dp[v] = 0;
    for (int j = 0; j < sz(c); ++j) dp[v] = max(dp[v], c[j] + j + 1);
    return dp[v];
}

void solve() {
    cin >> n >> A >> B;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    veci p;
    dfs(A);
    for (int i = B; i != A; i = par[i]) p.pb(i);
    int l = 0, r = sz(p) - 1, ans = 0;
    while (l <= r) {
        int mid = l + r >> 1;
        if (calc(A, 0, p[mid], par[p[mid]]) > calc(B, 0, p[mid], par[p[mid]])) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    int res = max(calc(A, 0, p[ans], par[p[ans]]), calc(B, 0, p[ans], par[p[ans]]));
    for(int i = max(0, ans - 1); i < min(sz(p), ans + 2); ++i) {
        res = min(res, max(calc(A, 0, p[i], par[p[i]]), calc(B, 0, p[i], par[p[i]])));
    }
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int CNT_TESTS = 1;
    // cin >> CNT_TESTS;
    for (int NUMCASE = 1; NUMCASE <= CNT_TESTS; ++NUMCASE) {
        solve();
        if (NUMCASE != CNT_TESTS) cout << '\n';
    }
    return 0;
}

Compilation message

torrent.cpp: In function 'void solve()':
torrent.cpp:72:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 3 ms 7636 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 25868 KB Output is correct
2 Correct 357 ms 27584 KB Output is correct
3 Correct 307 ms 29124 KB Output is correct
4 Correct 323 ms 28472 KB Output is correct
5 Correct 314 ms 25548 KB Output is correct
6 Correct 283 ms 25996 KB Output is correct
7 Correct 345 ms 29728 KB Output is correct