oj.uz

Submission #413843

# Submission time Handle Problem Language Result Execution time Memory
413843 2021-05-29T15:18:29 Z TruaShamu Torrent (COI16_torrent) C++14
100 / 100
 499 ms 27724 KB 
#include <bits/stdc++.h>

using namespace std;

struct Edge {
    int to;
    int index;
    Edge(int to, int index): to(to), index(index) {}
};

const int N = 3e5 + 5;

vector<int> path;
vector<int> temp;

vector<Edge> a[N];

int n, X, Y;
int cutEdge;

void dfsFindPath(int u, int p = 0) {
    if (!path.empty()) return;
    if (u == Y) {
        path = temp;
        return;
    }
    for (auto e : a[u]) {
        int v = e.to;
        if (v == p) continue;
        temp.push_back(e.index);
        dfsFindPath(v, u);
        temp.pop_back();
    }
}

int solve(int u, int p = 0) {
    int ans = 0;
    vector<int> V;
    for (auto e : a[u]) {
        int v = e.to;
        if (v == p) continue;
        if (e.index == cutEdge) continue;
        V.push_back(solve(v, u));
    }
    sort(V.begin(), V.end(), greater<int>());
    for (int i = 0; i < V.size(); ++i)
        ans = max(ans, V[i] + i + 1);
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> X >> Y;
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        a[u].push_back(Edge(v, i));
        a[v].push_back(Edge(u, i));
    }
    dfsFindPath(X);
    int l = 0, r = (int)path.size() - 1, last = 0;
    while (l <= r) {
        int mid = l + r >> 1;
        cutEdge = path[mid];
        int ansX = solve(X);
        int ansY = solve(Y);
        if (ansX <= ansY)
            last = mid, l = mid + 1;
        else
            r = mid - 1;
    }
    cutEdge = path[last];
    int ans = max(solve(X), solve(Y));
    if (last + 1 < path.size()) {
        cutEdge = path[last + 1];
        ans = min(ans, max(solve(X), solve(Y)));
    }
    cout << ans << endl;
    return 0;
}

Compilation message

torrent.cpp: In function 'int solve(int, int)':
torrent.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 0; i < V.size(); ++i)
      |                     ~~^~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:62:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |         int mid = l + r >> 1;
      |                   ~~^~~
torrent.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     if (last + 1 < path.size()) {
      |         ~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

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

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 20488 KB Output is correct
2 Correct 484 ms 25736 KB Output is correct
3 Correct 474 ms 27420 KB Output is correct
4 Correct 471 ms 26428 KB Output is correct
5 Correct 467 ms 24000 KB Output is correct
6 Correct 438 ms 24604 KB Output is correct
7 Correct 401 ms 27724 KB Output is correct