oj.uz

Submission #624768

# Submission time Handle Problem Language Result Execution time Memory
624768 2022-08-08T17:31:38 Z MohamedFaresNebili Torrent (COI16_torrent) C++14
100 / 100
 383 ms 27732 KB 
#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

            using namespace std;

            using ll = long long;
            using ld = long double;

            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound

            const int MOD = 998244353;

            int N, A, B, P[300005];
            vector<int> K, adj[300005];
            void dfs(int v, int p) {
                P[v] = p;
                if(v == B) {
                    while(v) {
                        K.push_back(v);
                        v = P[v];
                    }
                    return;
                }
                for(auto u : adj[v]) {
                    if(u == p) continue;
                    dfs(u, v);
                }
            }
            int solve(int v, int p, int r) {
                vector<int> E;
                for(auto u : adj[v]) {
                    if(u == p || u == r) continue;
                    E.push_back(solve(u, v, r));
                }
                sort(E.begin(), E.end());
                reverse(E.begin(), E.end());
                int res = -1;
                for(int l = 0; l < E.size(); l++) {
                    res = max(res, l + E[l]);
                }
                return res + 1;
            }

            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N >> A >> B;
                for(int l = 0; l < N - 1; l++) {
                    int U, V; cin >> U >> V;
                    adj[U].push_back(V);
                    adj[V].push_back(U);
                }
                dfs(A, 0); int res = N;
                int lo = 0, hi = K.size() - 1;
                while(lo <= hi) {
                    int md = (lo + hi) / 2;
                    int U = solve(A, 0, K[md]), V = solve(B, 0, K[md + 1]);
                    res = min(res, max(U, V));
                    if(U > V) lo = md + 1;
                    else hi = md - 1;
                }
                cout << res << "\n";
                return 0;
            }

Compilation message

torrent.cpp: In function 'int solve(int, int, int)':
torrent.cpp:44:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |                 for(int l = 0; l < E.size(); l++) {
      |                                ~~^~~~~~~~~~

Subtask #1
31.0 / 31.0

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

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 20240 KB Output is correct
2 Correct 350 ms 25748 KB Output is correct
3 Correct 357 ms 27312 KB Output is correct
4 Correct 370 ms 26628 KB Output is correct
5 Correct 369 ms 23868 KB Output is correct
6 Correct 321 ms 24564 KB Output is correct
7 Correct 383 ms 27732 KB Output is correct