oj.uz

Submission #637042

# Submission time Handle Problem Language Result Execution time Memory
637042 2022-08-31T10:18:47 Z MohamedFaresNebili Mousetrap (CEOI17_mousetrap) C++14
0 / 100
 900 ms 81120 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 = 0; i < C.size()/ 2; i++)
                    DP[v] += 1 + C[i];
                return DP[v] += (C.size() + 1) / 2;
            }
            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 = 0; i < C.size() / 2; i++)
                    res += 1 + C[i];
                return res + (C.size() + 1) / 2 + 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;
            }

Compilation message

mousetrap.cpp: In function 'int solve(int, int)':
mousetrap.cpp:26:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |                 for(int i = 0; i < C.size()/ 2; i++)
      |                                ~~^~~~~~~~~~~~~
mousetrap.cpp: In function 'int getAns(int, int)':
mousetrap.cpp:42:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |                 for(int i = 0; i < C.size() / 2; i++)
      |                                ~~^~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 23804 KB Output is correct
3 Correct 14 ms 23904 KB Output is correct
4 Correct 12 ms 23800 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 306 ms 80204 KB Output is correct
2 Correct 276 ms 74528 KB Output is correct
3 Incorrect 900 ms 81120 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 23804 KB Output is correct
3 Correct 14 ms 23904 KB Output is correct
4 Correct 12 ms 23800 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 12 ms 23764 KB Output is correct
2 Correct 14 ms 23804 KB Output is correct
3 Correct 14 ms 23904 KB Output is correct
4 Correct 12 ms 23800 KB Output is correct
5 Incorrect 12 ms 23812 KB Output isn't correct
6 Halted 0 ms 0 KB -