Submission #637066

#	Time	Username	Problem	Language	Result	Execution time	Memory
637066		MohamedFaresNebili	Mousetrap (CEOI17_mousetrap)	C++14	0 / 100	835 ms	68116 KiB

mousetrap

#include <bits/stdc++.h>
 
            using namespace std;
 
            const int INF = INT32_MAX;
 
            int N, T, M, DP[1000005];
            int timer, tin[1000005], out[1000005];
            vector<int> adj[1000005];
 
            void dfs(int v, int p) {
                tin[v] = timer++;
                for(auto u : adj[v]) {
                    if(u == p) continue;
                    dfs(u, v);
                }
                out[v] = timer - 1;
            }
            int solve(int v, int p) {
                vector<int> C;
                for(auto u : adj[v]) {
                    if(u == p) continue;
                    C.push_back(solve(u, v));
                }
                sort(C.begin(), C.end());
                for(int i = C.size() - 1, j = 0; ~i; i--, j++) {
                    if(j & 1) DP[v] += 1 + C[i];
                    else ++DP[v];
                }
                return DP[v];
            }
            int getAns(int v, int p) {
                if(v == T) return 0;
                int res = 0, nxt = -1;
                vector<int> C;
                for(auto u : adj[v]) {
                    if(u == p) continue;
                    if(tin[u] <= tin[T] && out[u] >= tin[T]) {
                        nxt = u; continue;
                    }
                    C.push_back(DP[u]);
                }
                sort(C.begin(), C.end());
                for(int i = C.size() - 1, j = 0; ~i; i--, j++) {
                    if(j & 1) res += 1 + C[i];
                    else ++res;
                }
                return res + getAns(nxt, v);
            }
 
            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N >> T >> M;
              	if(T == M) {
                  cout << 0; return 0;
                }
                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(M, M); solve(M, M);
                cout << getAns(M, M) << "\n";
                return 0;
            }

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