Submission #624768

#	Time	Username	Problem	Language	Result	Execution time	Memory
624768		MohamedFaresNebili	Torrent (COI16_torrent)	C++14	100 / 100	383 ms	27732 KiB

torrent

#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 (stderr)

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 / 31
• Subtask 2: 69 / 69