Submission #520060

#	Time	Username	Problem	Language	Result	Execution time	Memory
520060		KoD	Matching (COCI20_matching)	C++17	58 / 110	2532 ms	15600 KiB

matching

#include <bits/stdc++.h>

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

constexpr int MAX = 100000;

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;
    vector<int> X(N), Y(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> X[i] >> Y[i];
    }
    vector<vector<int>> graph(2 * N), revgraph(2 * N);
    const auto add_edge = [&](const int i, const int j) {
        graph[i].push_back(j);
        revgraph[j].push_back(i);
    };
    vector<pair<int, int>> vert, hori;
    vector<char> found(2 * N);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < i; ++j) {
            if (X[i] == X[j]) {
                if (Y[i] < Y[j]) {
                    vert.emplace_back(i, j);
                } else {
                    vert.emplace_back(j, i);
                }
                for (int k = 0; k < 2; ++k) {
                    add_edge(2 * i + k, 2 * j + k);
                    add_edge(2 * j + k, 2 * i + k);
                }
                found[2 * i] = found[2 * j] = true;
            } 
            if (Y[i] == Y[j]) {
                if (X[i] < X[j]) {
                    hori.emplace_back(i, j);
                } else {
                    hori.emplace_back(j, i);
                }
                for (int k = 0; k < 2; ++k) {
                    add_edge(2 * i + k, 2 * j + k);
                    add_edge(2 * j + k, 2 * i + k);
                }
                found[2 * i + 1] = found[2 * j + 1] = true;
            }
        }
    }
    for (int i = 0; i < 2 * N; ++i) {
        if (!found[i]) {
            add_edge(i, i ^ 1);
        }
    }
    for (const auto& [u, v] : vert) {
        for (const auto& [a, b] : hori) {
            if (X[a] < X[u] and X[u] < X[b] and Y[u] < Y[a] and Y[a] < Y[v]) {
                add_edge(2 * u, 2 * a);
                add_edge(2 * a + 1, 2 * u + 1);
            }
        }
    }
    vector<char> done(2 * N);
    vector<int> stack;
    for (int i = 0; i < 2 * N; ++i) {
        RecLambda([&](auto&& dfs, const int u) -> void {
            if (done[u]) {
                return;
            }
            done[u] = true;
            for (const int v : graph[u]) {
                dfs(v);
            }
            stack.push_back(u);
        })(i);
    }
    int idx = 0;
    vector<int> group(2 * N);
    std::fill(done.begin(), done.end(), false);
    while (!stack.empty()) {
        const int u = stack.back();
        stack.pop_back();
        RecLambda([&](auto&& dfs, const int u) -> void {
            if (done[u]) {
                return;
            }
            group[u] = idx;
            done[u] = true;
            for (const int v : revgraph[u]) {
                dfs(v);
            }
        })(u);
        idx += 1;
    }
    vector<char> type(N);
    for (int i = 0; i < N; ++i) {
        if (group[2 * i] == group[2 * i + 1]) {
            std::cout << "NE\n";
            return 0;
        }
        type[i] = group[2 * i] > group[2 * i + 1];
    }
    std::cout << "DA\n";
    for (const auto& [u, v] : vert) {
        if (type[u]) {
            std::cout << u + 1 << ' ' << v + 1 << std::endl;
        }
    }
    for (const auto& [u, v] : hori) {
        if (!type[u]) {
            std::cout << u + 1 << ' ' << v + 1 << std::endl;
        }
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 40 / 40
• Subtask 5: 0 / 52