oj.uz

Submission #846681

# Submission time Handle Problem Language Result Execution time Memory
846681 2023-09-08T08:58:00 Z vjudge1 Torrent (COI16_torrent) C++17
100 / 100
 276 ms 25216 KB 
#include <bits/stdc++.h>

using namespace std;
#define task "code"

const int ar = 3e5 + 1;
const int inf = 1e9 + 5;

int n, a, b, u, v, dp[ar], res = inf;
vector<int> adj[ar];
vector< pair<int, int> > vec;

bool c = false;
void find_dfs(int u, int p) {
    if (u == b) {
        c = true;
        return;
    }
    for (int v : adj[u]) if (v != p) {
        find_dfs(v, u);
        if (c == true) {
            vec.push_back({u, v});
            return ;
        }
    }
}

int dfs (int u, int p, int x) {
    vector<int> vc;
    for (int v : adj[u])
        if (v != p && v != x)
            vc.push_back(dfs(v, u, x));

    int ans = 0;
    sort (vc.begin(), vc.end(), greater<int>());
    for (int i = 0; i < vc.size(); ++ i)
        ans = max(ans, vc[i] + i + 1);

//    cout << u << ' ' << p << ' ' << ans << '\n';
//    cout << "vc: ";
//    for (int x : vc) cout << x << ' '; cout << '\n';
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

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

    if (a == b) return cout << dfs(a, 0, 0), 0;
    find_dfs(a, 0);
//    for (auto x : vec) cout << x.first << ' ' << x.second << '\n'; cout << '\n';
    if (n <= 1000) {
        for (auto x : vec) {
            int valA = dfs(a, 0, x.second), valB = dfs(b, 0, x.first);
            res = min(res, max(valA, valB));
        }
    }
    else {
        int l = 0, r = vec.size() - 1;
        while (l <= r) {
            int m = l + r >> 1;
    //        cout << vec[m].first << ' ' << vec[m].second << '\n';
            int valA = dfs(a, 0, vec[m].second), valB = dfs(b, 0, vec[m].first);
            res = min(res, max(valA, valB));
            if (valA >= valB) r = m - 1;
            else l = m + 1;
        }
    }
    cout << res;

    return 0;
}

Compilation message

torrent.cpp: In function 'int dfs(int, int, int)':
torrent.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 0; i < vc.size(); ++ i)
      |                     ~~^~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:68:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |             int m = l + r >> 1;
      |                     ~~^~~

Subtask #1
31.0 / 31.0

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

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 19620 KB Output is correct
2 Correct 259 ms 21356 KB Output is correct
3 Correct 262 ms 23912 KB Output is correct
4 Correct 236 ms 21960 KB Output is correct
5 Correct 276 ms 19200 KB Output is correct
6 Correct 227 ms 19928 KB Output is correct
7 Correct 235 ms 25216 KB Output is correct