oj.uz

Submission #891839

# Submission time Handle Problem Language Result Execution time Memory
891839 2023-12-24T08:10:58 Z Beerus13 Torrent (COI16_torrent) C++14
100 / 100
 305 ms 30940 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int ar = 3e5 + 5;

int n, a, b, par[ar];
vector<int> adj[ar];
int dp[ar];
int del, ans = 1e9;

void build_tree(int u, int p) {
    for(int v : adj[u]) if(v != p){
        par[v] = u;
        build_tree(v, u);
    }
}

void dfs(int u, int p) {
    dp[u] = 0;
    priority_queue<int> q;
    for(int v : adj[u]) if(v != p && v != del) {
        dfs(v, u);
        q.push(dp[v]);
    }
    int cnt = 1;
    while(q.size()) {
        dp[u] = max(dp[u], cnt + q.top());
        q.pop();
        ++cnt;
    }
}

bool check(int u, int v) {
    del = v;
    dfs(a, 0);
    del = u;
    dfs(b, 0);
    ans = min(ans, max(dp[a], dp[b]));
    return dp[u] > dp[v];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> a >> b;
    for(int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    build_tree(a, 0);
    if(a == b) {
        dfs(a, 0);
        return cout << dp[a], 0;
    }
    vector<int> road;
    int tmp = b; while(tmp != a) {
        road.push_back(tmp);
        tmp = par[tmp];
    }
    if(n <= 1000) {
        for(int x : road) check(par[x], x);
        return cout << ans, 0;
    }
    int l = 0, r = road.size() - 1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(check(par[road[mid]], road[mid])) l = mid + 1;
        else r = mid - 1;
    }
    cout << ans;
}

Compilation message

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

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8540 KB Output is correct
2 Correct 4 ms 8540 KB Output is correct
3 Correct 7 ms 8536 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 25932 KB Output is correct
2 Correct 295 ms 27592 KB Output is correct
3 Correct 289 ms 30824 KB Output is correct
4 Correct 305 ms 28292 KB Output is correct
5 Correct 280 ms 25680 KB Output is correct
6 Correct 243 ms 25944 KB Output is correct
7 Correct 275 ms 30940 KB Output is correct