oj.uz

Submission #846669

# Submission time Handle Problem Language Result Execution time Memory
846669 2023-09-08T08:46:41 Z vjudge1 Torrent (COI16_torrent) C++14
69 / 100
 588 ms 26788 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 check1(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];
}

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

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) check1(par[x], x);
    //     return cout << ans, 0;
    // }
    int l = 0, r = road.size() - 1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(check1(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(check2(par[road[mid]], road[mid])) r = mid - 1;
        else l = mid + 1;
    }
    cout << ans;
}

Compilation message

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

Subtask #1
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8540 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 588 ms 22032 KB Output is correct
2 Correct 576 ms 23800 KB Output is correct
3 Correct 506 ms 26696 KB Output is correct
4 Correct 548 ms 24800 KB Output is correct
5 Correct 555 ms 21648 KB Output is correct
6 Correct 477 ms 21864 KB Output is correct
7 Correct 506 ms 26788 KB Output is correct