oj.uz

Submission #515988

# Submission time Handle Problem Language Result Execution time Memory
515988 2022-01-20T09:08:11 Z KoD Magenta (COCI21_magenta) C++17
30 / 110
 68 ms 8260 KB 
#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

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;
    std::cin >> N;
    array<int, 2> root;
    for (auto& x : root) {
        std::cin >> x;
        x -= 1;
    }
    vector<vector<pair<int, int>>> graph(N);
    for (int i = 1; i < N; ++i) {
        int u, v;
        std::string s;
        std::cin >> u >> v >> s;
        u -= 1, v -= 1;
        const int k = (s == "plava" ? 0 : (s == "crvena" ? 1 : 2));
        graph[u].emplace_back(v, k);
        graph[v].emplace_back(u, k);
    }
    array<vector<int>, 2> depth = {}, parent = {};
    array<vector<char>, 2> reach = {};
    for (int k = 0; k < 2; ++k) {
        depth[k] = vector<int>(N);
        parent[k] = vector<int>(N);
        reach[k] = vector<char>(N);
        depth[k][root[k]] = 0;
        parent[k][root[k]] = -1;
        reach[k][root[k]] = true;
        RecLambda([&](auto&& dfs, const int u) -> void {
            for (const auto& [v, c] : graph[u]) {
                if (v != parent[k][u]) {
                    depth[k][v] = depth[k][u] + 1;
                    parent[k][v] = u;
                    reach[k][v] = reach[k][u] and (c != (k ^ 1));
                    dfs(v);
                }
            }
        })(root[k]);
    }
    if (std::count(reach[0].begin(), reach[0].end(), true) == 1) {
        std::cout << "Marin\n";
        return 0;
    }
    if (std::count(reach[1].begin(), reach[1].end(), true) == 1) {
        std::cout << "Paula\n";
        return 0;
    }
    const int length = depth[0][root[1]];
    const int type = length % 2;
    vector<char> good(N);
    for (int u = 0; u < N; ++u) {
        if (reach[type][u] or !reach[type ^ 1][u]) {
            continue;
        }
        for (const auto& [v, c] : graph[u]) {
            if (!reach[type][v] and reach[type ^ 1][v]) {
                good[u] = true;
                break;
            }
        }
    }
    int src = root[type];
    for (int i = 0; i <= length / 2; ++i) {
        src = parent[type ^ 1][src];
    }
    if (RecLambda([&](auto&& dfs, const int u) -> bool {
        if (good[u]) {
            return true;
        }
        for (const auto& [v, k] : graph[u]) {
            if (v != parent[type][u] and dfs(v)) {
                return true;
            }
        }
        return false;
    })(src)) {
        std::cout << "Magenta\n";
        assert(false);
    } else {
        std::cout << (type == 0 ? "Paula" : "Marin") << '\n';
    }
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Runtime error 1 ms 460 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 8196 KB Output is correct
2 Correct 53 ms 8260 KB Output is correct
3 Correct 57 ms 8248 KB Output is correct
4 Correct 51 ms 8132 KB Output is correct
5 Correct 68 ms 8184 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Runtime error 1 ms 460 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -