oj.uz

답안 #637074

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
637074 2022-08-31T12:16:46 Z MohamedFaresNebili Mousetrap (CEOI17_mousetrap) C++14
0 / 100
 1638 ms 289048 KB 
#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();
                }
                int U = pq[v].top();
                while(pq[v].size()) pq[v].pop();
                pq[v].push(U);
            }

            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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 65 ms 111564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 716 ms 287956 KB Output is correct
2 Correct 646 ms 264712 KB Output is correct
3 Incorrect 1638 ms 289048 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 65 ms 111564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 65 ms 111564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -