Submission #624755

#	Time	Username	Problem	Language	Result	Execution time	Memory
624755		MohamedFaresNebili	Torrent (COI16_torrent)	C++14	0 / 100	98 ms	24896 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;
            vector<int> adj[300005];
            int DP[300005];

            void dfs(int v, int p) {
                int C = 1;
                for(auto u : adj[v]) {
                    if(u == p) continue;
                    if(DP[u] > DP[v] + C) {
                        DP[u] = min(DP[u], DP[v] + C);
                        ++C;
                    }
                    dfs(u, v);
                }
            }

            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);
                }
                for(int l = 1; l <= N; l++) DP[l] = 2e9;
                DP[A] = 0; dfs(A, A);
                DP[B] = 0; dfs(B, B); int res = 0;
                for(int l = 1; l <= N; l++)
                    res = max(res, DP[l]);
                cout << res << "\n";
                return 0;
            }

• Subtask 1: 0 / 31
• Subtask 2: 0 / 69