oj.uz

Submission #846649

# Submission time Handle Problem Language Result Execution time Memory
846649 2023-09-08T08:18:11 Z LaziChicken Torrent (COI16_torrent) C++17
100 / 100
 306 ms 26520 KB 
//LaziChicken - 9/2023

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pli pair <ll, int>
#define pil pair <int, ll>
#define fi first
#define se second
#define dim 3
#define tii tuple <int, int, int>
#define inf 0x3f

const ll nx = 3e5+2;
const ll bx = 1e3+2;
const ll mod = 1e9+7;

//--------------------------------
int n, a, b, pre[nx];
int res = 1e9, dist[2][nx];
vector <int> adj[nx], trace;

void dfstrace(int par, int u){
    for (auto v : adj[u]){
        if (v == par) continue;
        pre[v] = u;
        dfstrace(u, v);
    }
}

int dfs(bool dir, int par, int u, int ban){
    vector <int> vt;
    for (auto v : adj[u]){
        if (v == par or v == ban) continue;
        vt.emplace_back(dfs(dir, u, v, ban));
    }
    sort(vt.begin(), vt.end(), greater<int>());
    for (int i = 0; i < vt.size(); i++){
        dist[dir][u] = max(dist[dir][u], vt[i] + i + 1);
    }
    return dist[dir][u];
}

bool check(int mid){
    memset(dist, 0, sizeof(dist));
    dfs(0, 0, a, trace[mid+1]);
    dfs(1, 0, b, trace[mid]);
    res = min(res, max(dist[0][a], dist[1][b]));
    return dist[0][a] < dist[1][b];
}

void bs(int l, int r){
    while(l <= r){
        int mid = (l + r) >> 1;
        if (check(mid)) l = mid + 1;
        else r = mid - 1;
    }
}

//--------------------------------
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> a >> b;
    for (int i = 1, u, v; i < n; i++){
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    dfstrace(0, a);
    int tmp = b; trace.emplace_back(b);
    while(tmp != a){
        if (tmp != b and tmp != a) trace.emplace_back(tmp);
        tmp = pre[tmp];
    }
    trace.emplace_back(a);
    reverse(trace.begin(), trace.end());
    bs(0, trace.size() - 2);
    cout << res;
}
/*
Note:

*/

Compilation message

torrent.cpp: In function 'int dfs(bool, int, int, int)':
torrent.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < vt.size(); i++){
      |                     ~~^~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10840 KB Output is correct
2 Correct 4 ms 10848 KB Output is correct
3 Correct 3 ms 10840 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 23024 KB Output is correct
2 Correct 306 ms 24372 KB Output is correct
3 Correct 264 ms 26192 KB Output is correct
4 Correct 293 ms 25572 KB Output is correct
5 Correct 277 ms 22352 KB Output is correct
6 Correct 257 ms 23040 KB Output is correct
7 Correct 298 ms 26520 KB Output is correct