oj.uz

Submission #846672

# Submission time Handle Problem Language Result Execution time Memory
846672 2023-09-08T08:48:31 Z vjudge1 Torrent (COI16_torrent) C++17
100 / 100
 349 ms 23808 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;

#define eb emplace_back
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()

int n, a, b;
vector<int> adj[N];
vector<pii> path;
int par[N];

void get(int u, int p) {
    for(int v : adj[u]) {
        if(v == p) continue;

        par[v] = u;
        get(v, u);
    }
}

int DFS(int u, int p, pii block) {
    int sum = 0;
    vector<int> res;

    for(int v : adj[u]) {
        if(v == p)
            continue;

        if(make_pair(u, v) == block or make_pair(v, u) == block)
            continue;

        res.eb(DFS(v, u, block));
    }

    sort(all(res));
    reverse(all(res));

    for(int i = 0; i < sz(res); i++)
        sum = max(sum, res[i] + (i + 1));

    return sum;
}

void process() {
    get(a, 0);
    int x = b;

    while(x != a) {
        path.eb(par[x], x);
        x = par[x];
    }

    reverse(all(path));
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> a >> b;

    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].eb(v);
        adj[v].eb(u);
    }

    process();
    int l = 0, r = sz(path) - 1;

    while(r - l > 1) {
        int m = l + r >> 1;
        int x = DFS(a, 0, path[m]);
        int y = DFS(b, 0, path[m]);

        if(x < y) {
            l = m;

        } else r = m;
    }

    int ans = max(DFS(a, 0, path[l]), DFS(b, 0, path[l]));
    ans = min(ans, max(DFS(a, 0, path[r]), DFS(b, 0, path[r])));
    cout << ans;
}
//

Compilation message

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

Subtask #1
31.0 / 31.0

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

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 20456 KB Output is correct
2 Correct 349 ms 21916 KB Output is correct
3 Correct 287 ms 23456 KB Output is correct
4 Correct 327 ms 22732 KB Output is correct
5 Correct 274 ms 19796 KB Output is correct
6 Correct 257 ms 20568 KB Output is correct
7 Correct 272 ms 23808 KB Output is correct