Submission #515990

#	Time	Username	Problem	Language	Result	Execution time	Memory
515990		KoD	Magenta (COCI21_magenta)	C++17	30 / 110	74 ms	8288 KiB

Main

#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 (!reach[type][src]) {
            break;
        }
    }
    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";
    } else {
        std::cout << (type == 0 ? "Paula" : "Marin") << '\n';
    }
    return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 50