Submission #637042

#	Time	Username	Problem	Language	Result	Execution time	Memory
637042		MohamedFaresNebili	Mousetrap (CEOI17_mousetrap)	C++14	0 / 100	900 ms	81120 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 = 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 (stderr)

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
• Subtask 2: 0 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35