Submission #637075

#	Time	Username	Problem	Language	Result	Execution time	Memory
637075		MohamedFaresNebili	Mousetrap (CEOI17_mousetrap)	C++14	0 / 100	1587 ms	289364 KiB

mousetrap

#include <bits/stdc++.h>
 
            using namespace std;
 
            const int INF = INT32_MAX;
            const int LOG = 20;
 
            int N, T, M;
            int P[1000005][20], S[1000005][20], dep[1000005];
            int timer, tin[1000005], out[1000005];
            priority_queue<int, vector<int>, greater<int>> pq[1000005];
            vector<int> leaves; vector<int> adj[1000005];
            void dfs(int v, int p) {
                P[v][0] = p; dep[v] = dep[p] + 1;
                tin[v] = timer++;
                int children = 0;
                for(auto u : adj[v]) {
                    if(u == p) continue;
                    ++children; dfs(u, v);
                }
                for(auto u : adj[v]) {
                    if(u == p) continue;
                    S[u][0] = children;
                }
                out[v] = timer - 1;
                if(v == T && children == 0) pq[v].push(0);
            }
            void solve(int v, int p) {
                int children = 0;
                for(auto u : adj[v]) {
                    if((u == p))
                        continue;
                    if(u != T) solve(u, v);
                    ++children;
                }
                if(children == 0) leaves.push_back(v);
            }
            int dist(int u, int v) {
                bool swp = 0;
                if(dep[u] < dep[v]) swap(u, v), swp = 1;
                int K = dep[u] - dep[v];
                int x = u, y = v, cur = 0;
                for(int l = 0; l < LOG; l++)
                    if(K & (1 << l)) cur += S[x][l], x = P[x][l];
                if(x != y) {
                    for(int l = LOG - 1; ~l; l--) {
                        if(P[x][l] != P[y][l]) {
                            cur += S[x][l], cur += S[y][l];
                            x = P[x][l], y = P[y][l];
                        }
                    }
                    cur += S[x][0]; x = P[x][0];
                }
                if(swp) swap(u, v);
                int D = cur - dep[v] + dep[x];
                return D;
            }
            void propagate(int v, int p) {
                for(auto u : adj[v]) {
                    if(u == p) continue;
                    propagate(u, v);
                    pq[v].push({pq[u].top()});
                    while(pq[v].size() > 2) pq[v].pop();
                }
            }
 
            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N >> T >> M;
                for(int l = 0; l < N - 1; l++) {
                    int U, V; cin >> U >> V;
                    adj[U].push_back(V);
                    adj[V].push_back(U);
                }
                dep[M] = -1; dfs(M, M); solve(M, M);
                for(int i = 1; i < LOG; i++)
                    for(int l = 1; l <= N; l++) {
                        P[l][i] = P[P[l][i - 1]][i - 1];
                        S[l][i] = S[l][i - 1] + S[P[l][i - 1]][i - 1];
                    }
                for(auto u : leaves)
                    pq[u].push(dist(u, T));
                propagate(M, M);
                cout << pq[M].top();
                return 0;
            }

• Subtask 1: 0 / 20
• Subtask 2: 0 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35