oj.uz

Submission #846628

# Submission time Handle Problem Language Result Execution time Memory
846628 2023-09-08T07:49:30 Z tuan13 Torrent (COI16_torrent) C++14
69 / 100
 595 ms 26828 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];
    }
    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;
    }
    l = 0, r = road.size() - 1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(!check(par[road[mid]], road[mid])) r = mid - 1;
        else l = mid + 1;
    }
    cout << ans;
}

Compilation message

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

Subtask #1
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 595 ms 21840 KB Output is correct
2 Correct 568 ms 23512 KB Output is correct
3 Correct 568 ms 26740 KB Output is correct
4 Correct 545 ms 23936 KB Output is correct
5 Correct 583 ms 21652 KB Output is correct
6 Correct 466 ms 21928 KB Output is correct
7 Correct 526 ms 26828 KB Output is correct