oj.uz

Submission #434686

# Submission time Handle Problem Language Result Execution time Memory
434686 2021-06-21T14:49:39 Z KoD Mousetrap (CEOI17_mousetrap) C++17
45 / 100
 1391 ms 68940 KB 
#include <bits/stdc++.h>

template <class T> using Vec = std::vector<T>;

template <class F> struct RecLambda : private F {
    explicit RecLambda(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator() (Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, T, M;
    std::cin >> N >> T >> M;
    T -= 1;
    M -= 1;
    Vec<Vec<int>> graph(N);
    for (int i = 0; i < N - 1; ++i) {
        int a, b;
        std::cin >> a >> b;
        a -= 1;
        b -= 1;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    Vec<int> parent(N, -1);
    RecLambda([&](auto&& dfs, const int u) -> void {
        for (const int v : graph[u]) {
            if (parent[u] != v) {
                parent[v] = u;
                dfs(v);
            }
        }
    })(T);
    Vec<int> dp(N, -1);
    Vec<char> used(N);
    const auto down = RecLambda([&](auto&& dfs, const int u) -> int {
        if (dp[u] != -1) {
            return dp[u];
        }
        Vec<int> cand;
        for (const int v : graph[u]) {
            if (v != parent[u] and !used[v]) {
                cand.push_back(dfs(v));
            }
        } 
        std::sort(cand.rbegin(), cand.rend());
        if (cand.size() <= 1) {
            return dp[u] = (int) cand.size();
        }
        return dp[u] = cand[1] + (int) cand.size();
    });
    Vec<int> cut(N);
    RecLambda([&](auto&& dfs, const int u) -> void {
        for (const int v : graph[u]) {
            if (parent[u] != v) {
                cut[v] += cut[u];
                if (u != T) {
                    cut[v] += (int) graph[u].size() - 2;
                }
                dfs(v);
            }
        }
    })(T);
    std::cout << cut[M] + down(M) << '\n';
    // std::cout << RecLambda([&](auto&& dfs, const int u) -> int {
    //     if (u == T) {
    //         return 0;
    //     }
    //     used[u] = true;
    //     int dmax = 0;
    //     for (const int v : graph[u]) {
    //         if (parent[u] != v and !used[v]) {
    //             dmax = std::max(dmax, down(v) + 1);
    //         }
    //     }
    //     return std::min(dmax + cut[u] + 2, std::max(down(u) + cut[u], dfs(parent[u]) + 1));
    // })(M) << '\n';
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 67724 KB Output is correct
2 Correct 373 ms 61072 KB Output is correct
3 Correct 1391 ms 68932 KB Output is correct
4 Correct 606 ms 34632 KB Output is correct
5 Correct 1387 ms 68940 KB Output is correct
6 Correct 1316 ms 68932 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Incorrect 1 ms 204 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 429 ms 67724 KB Output is correct
12 Correct 373 ms 61072 KB Output is correct
13 Correct 1391 ms 68932 KB Output is correct
14 Correct 606 ms 34632 KB Output is correct
15 Correct 1387 ms 68940 KB Output is correct
16 Correct 1316 ms 68932 KB Output is correct
17 Incorrect 1 ms 204 KB Output isn't correct
18 Halted 0 ms 0 KB -