oj.uz

Submission #669666

# Submission time Handle Problem Language Result Execution time Memory
669666 2022-12-07T04:14:05 Z ziduo Mousetrap (CEOI17_mousetrap) C++14
100 / 100
 1034 ms 204476 KB 
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>
 
            using namespace std;
 
            const int INF = INT32_MAX;
 
            int N, T, M, P[1000005], rem[1000005];
            int DP[1000005], deg[1000005], S[1000005];
            vector<int> adj[1000005], C[1000005];
 
            void dfs(int v, int p) {
                if(v == M) rem[v] = 1;
                for(auto u : adj[v]) {
                    if(u == p) continue;
                    dfs(u, v); P[u] = v;
                    if(rem[u]) rem[v] = 1;
                    else {
                        C[v].push_back(u); ++deg[v];
                    }
                }
                sort(C[v].begin(), C[v].end(), [](int A, int B) { return DP[A] > DP[B]; });
                if(C[v].size() <= 1) DP[v] = deg[v];
                else DP[v] = deg[v] + DP[C[v][1]];
            }
            void dfs(int v) {
                DP[v] += S[v];
                for(auto u : adj[v]) {
                    if(u == P[v]) continue;
                    S[u] = S[v] + deg[v]; dfs(u);
                }
            }
            bool possible(int v) {
                int cur = 0, dep = 0;
                for(int e = M; e != T; e = P[e]) {
                    ++dep; int k = 0;
                    for(auto u : C[e]) {
                        if(DP[u] + cur - k > v) ++cur, ++k;
                    }
                    if(cur > dep || cur > v)
                        return false;
                }
                return true;
            }
 
            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(T, T); deg[T] = 0; dfs(T);
                int lo = 0, hi = N, ans = -1;
                while(lo <= hi) {
                    int md = (lo + hi) / 2;
                    if(possible(md)) ans = md, hi = md - 1;
                    else lo = md + 1;
                }
                cout << ans << "\n";
                return 0;
            }

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47316 KB Output is correct
2 Correct 24 ms 47316 KB Output is correct
3 Correct 27 ms 47236 KB Output is correct
4 Correct 24 ms 47308 KB Output is correct
5 Correct 23 ms 47276 KB Output is correct
6 Correct 23 ms 47292 KB Output is correct
7 Correct 23 ms 47312 KB Output is correct
8 Correct 23 ms 47316 KB Output is correct
9 Correct 22 ms 47236 KB Output is correct
10 Correct 22 ms 47292 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 107932 KB Output is correct
2 Correct 302 ms 102456 KB Output is correct
3 Correct 962 ms 112144 KB Output is correct
4 Correct 457 ms 80000 KB Output is correct
5 Correct 969 ms 112076 KB Output is correct
6 Correct 1006 ms 112308 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47316 KB Output is correct
2 Correct 24 ms 47316 KB Output is correct
3 Correct 27 ms 47236 KB Output is correct
4 Correct 24 ms 47308 KB Output is correct
5 Correct 23 ms 47276 KB Output is correct
6 Correct 23 ms 47292 KB Output is correct
7 Correct 23 ms 47312 KB Output is correct
8 Correct 23 ms 47316 KB Output is correct
9 Correct 22 ms 47236 KB Output is correct
10 Correct 22 ms 47292 KB Output is correct
11 Correct 23 ms 47316 KB Output is correct
12 Correct 22 ms 47396 KB Output is correct
13 Correct 24 ms 47316 KB Output is correct
14 Correct 27 ms 47564 KB Output is correct
15 Correct 24 ms 47428 KB Output is correct
16 Correct 26 ms 47320 KB Output is correct
17 Correct 24 ms 47280 KB Output is correct
18 Correct 25 ms 47316 KB Output is correct
19 Correct 23 ms 47316 KB Output is correct
20 Correct 24 ms 47316 KB Output is correct
21 Correct 24 ms 47316 KB Output is correct
22 Correct 23 ms 47356 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47316 KB Output is correct
2 Correct 24 ms 47316 KB Output is correct
3 Correct 27 ms 47236 KB Output is correct
4 Correct 24 ms 47308 KB Output is correct
5 Correct 23 ms 47276 KB Output is correct
6 Correct 23 ms 47292 KB Output is correct
7 Correct 23 ms 47312 KB Output is correct
8 Correct 23 ms 47316 KB Output is correct
9 Correct 22 ms 47236 KB Output is correct
10 Correct 22 ms 47292 KB Output is correct
11 Correct 343 ms 107932 KB Output is correct
12 Correct 302 ms 102456 KB Output is correct
13 Correct 962 ms 112144 KB Output is correct
14 Correct 457 ms 80000 KB Output is correct
15 Correct 969 ms 112076 KB Output is correct
16 Correct 1006 ms 112308 KB Output is correct
17 Correct 23 ms 47316 KB Output is correct
18 Correct 22 ms 47396 KB Output is correct
19 Correct 24 ms 47316 KB Output is correct
20 Correct 27 ms 47564 KB Output is correct
21 Correct 24 ms 47428 KB Output is correct
22 Correct 26 ms 47320 KB Output is correct
23 Correct 24 ms 47280 KB Output is correct
24 Correct 25 ms 47316 KB Output is correct
25 Correct 23 ms 47316 KB Output is correct
26 Correct 24 ms 47316 KB Output is correct
27 Correct 24 ms 47316 KB Output is correct
28 Correct 23 ms 47356 KB Output is correct
29 Correct 24 ms 47288 KB Output is correct
30 Correct 357 ms 108492 KB Output is correct
31 Correct 332 ms 108624 KB Output is correct
32 Correct 412 ms 172988 KB Output is correct
33 Correct 380 ms 204476 KB Output is correct
34 Correct 1034 ms 112252 KB Output is correct
35 Correct 1025 ms 112296 KB Output is correct
36 Correct 998 ms 120076 KB Output is correct
37 Correct 1004 ms 120080 KB Output is correct
38 Correct 711 ms 111752 KB Output is correct
39 Correct 683 ms 111600 KB Output is correct
40 Correct 695 ms 111676 KB Output is correct