oj.uz

Submission #637066

# Submission time Handle Problem Language Result Execution time Memory
637066 2022-08-31T11:37:24 Z MohamedFaresNebili Mousetrap (CEOI17_mousetrap) C++14
0 / 100
 835 ms 68116 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23800 KB Output is correct
3 Correct 12 ms 23824 KB Output is correct
4 Correct 11 ms 23764 KB Output is correct
5 Incorrect 12 ms 23812 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 64972 KB Output is correct
2 Correct 312 ms 60916 KB Output is correct
3 Incorrect 835 ms 68116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23800 KB Output is correct
3 Correct 12 ms 23824 KB Output is correct
4 Correct 11 ms 23764 KB Output is correct
5 Incorrect 12 ms 23812 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23800 KB Output is correct
3 Correct 12 ms 23824 KB Output is correct
4 Correct 11 ms 23764 KB Output is correct
5 Incorrect 12 ms 23812 KB Output isn't correct
6 Halted 0 ms 0 KB -