oj.uz

Submission #637043

# Submission time Handle Problem Language Result Execution time Memory
637043 2022-08-31T10:22:33 Z MohamedFaresNebili Mousetrap (CEOI17_mousetrap) C++14
0 / 100
 848 ms 68040 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;
                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 15 ms 23764 KB Output is correct
2 Correct 16 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Incorrect 12 ms 23788 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 64960 KB Output is correct
2 Correct 289 ms 60740 KB Output is correct
3 Incorrect 848 ms 68040 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 35.0

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