oj.uz

Submission #846624

# Submission time Handle Problem Language Result Execution time Memory
846624 2023-09-08T07:43:21 Z vjudge1 Torrent (COI16_torrent) C++17
69 / 100
 335 ms 28836 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][2];
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, bool c) {
    dp[u][c] = 0;
    priority_queue<int> q;
    for(int v : adj[u]) if(v != p && v != del) {
        dfs(v, u, c);
        q.push(dp[v][c]);
    }
    int cnt = 1;
    while(q.size()) {
        dp[u][c] = max(dp[u][c], cnt + q.top());
        q.pop();
        ++cnt;
    }
}

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

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);
    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;
    }
    cout << ans;
}

Compilation message

torrent.cpp: In function 'int main()':
torrent.cpp:59:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |         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 290 ms 22976 KB Output is correct
2 Correct 296 ms 25108 KB Output is correct
3 Correct 335 ms 28836 KB Output is correct
4 Correct 293 ms 25584 KB Output is correct
5 Correct 294 ms 22860 KB Output is correct
6 Correct 257 ms 23448 KB Output is correct
7 Correct 271 ms 28764 KB Output is correct