oj.uz

Submission #286857

# Submission time Handle Problem Language Result Execution time Memory
286857 2020-08-31T05:42:53 Z two_sides Torrent (COI16_torrent) C++17
100 / 100
 472 ms 28916 KB 
#include <bits/stdc++.h>
using namespace std;

#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

const int N = 300005;

vector <int> g[N];
vector <int> cur, path;
int n, a, b, dp[N];

void dfs1(int u, int p) {
    cur.eb(u);
    if (u == b) path = cur;
    for (int v : g[u])
        if (v != p) dfs1(v, u);
    cur.pop_back();
}

void dfs2(int u, int p, int exc) {
    dp[u] = 0;
    if (u == exc) return;
    for (int v : g[u])
        if (v != p && v != exc)
            dfs2(v, u, exc);
    cur.clear();
    for (int v : g[u])
        if (v != p && v != exc)
            cur.eb(dp[v]);
    sort(rall(cur));
    for (int i = 0; i < cur.size(); i++)
        dp[u] = max(dp[u], cur[i] + i + 1);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> a >> b;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].eb(v); g[v].eb(u);
    }
    dfs1(a, 0); dfs2(a, 0, 0);
    int res = dp[a];
    int lo = 0, hi = path.size() - 2;
    while (lo <= hi) {
        int mi = (lo + hi) / 2;
        dfs2(a, 0, path[mi + 1]);
        dfs2(b, 0, path[mi]);
        res = min(res, max(dp[a], dp[b]));
        if (dp[a] < dp[b]) lo = mi + 1;
        else hi = mi - 1;
    }
    cout << res << '\n';
}

Compilation message

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

Subtask #1
31.0 / 31.0

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

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 24568 KB Output is correct
2 Correct 458 ms 26360 KB Output is correct
3 Correct 397 ms 28516 KB Output is correct
4 Correct 360 ms 26996 KB Output is correct
5 Correct 383 ms 24184 KB Output is correct
6 Correct 324 ms 25092 KB Output is correct
7 Correct 290 ms 28916 KB Output is correct