oj.uz

Submission #916583

# Submission time Handle Problem Language Result Execution time Memory
916583 2024-01-26T06:37:29 Z 406 Torrent (COI16_torrent) C++17
100 / 100
 441 ms 29480 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 50;
bitset<N> mark;
vector<int> adj[N];
int par[N], n, a, b, dp[N];

void dfs_path(int v) {
    mark[v] = true;
    for (auto u: adj[v])
        if (!mark[u]) {
            par[u] = v;
            dfs_path(u);
        }
}

void dfs(int v) {
    mark[v] = true;
    vector<int> vc;
    for (auto u: adj[v]) {
        if (!mark[u]) {
            dfs(u);
            vc.push_back(dp[u]);
        }
    }
    sort(vc.rbegin(), vc.rend());
    dp[v] = 0;
    for (int i = 0; i < vc.size(); i++)
        dp[v] = max(dp[v], vc[i] + i + 1);
}

int check(int a, int O) {
    mark = 0;
    mark[O] = true;
    dfs(a);
    return dp[a];
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> a >> b;
    assert(a != b);
    a--, b--;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs_path(a);

    vector<int> path{b};
    while (path.back() != a) 
        path.push_back(par[path.back()]);

    int l = 0, r = path.size() - 1;
    while (r - l > 3) {
        int mid = (r + l) / 2;
        if (check(b, path[mid + 1]) > check(a, path[mid])) 
            r = mid;
        else
            l = mid;
    }
    int ans = n;
    for (; l < r; l++)
        ans = min(ans, max(check(b, path[l + 1]), check(a, path[l])));
    cout << ans << '\n';
    return 0;
}

Compilation message

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

Subtask #1
31.0 / 31.0

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

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 26008 KB Output is correct
2 Correct 441 ms 27560 KB Output is correct
3 Correct 361 ms 29420 KB Output is correct
4 Correct 373 ms 28728 KB Output is correct
5 Correct 351 ms 25604 KB Output is correct
6 Correct 287 ms 26080 KB Output is correct
7 Correct 310 ms 29480 KB Output is correct