Submission #509702

#	Time	Username	Problem	Language	Result	Execution time	Memory
509702		KoD	Kutije (COCI21_kutije)	C++17	70 / 70	177 ms	10368 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, M, Q;
    std::cin >> N >> M >> Q;
    vector edge(N, vector<char>(N));
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            int p;
            std::cin >> p;
            edge[p - 1][j] = true;
        }
    }
    vector<std::bitset<1000>> reach(N);
    vector<char> done(N);
    vector<int> list;
    const auto forward = RecLambda([&](auto&& dfs, const int u) -> void {
        if (done[u]) return;
        done[u] = true;
        for (int i = 0; i < N; ++i) {
            if (edge[u][i]) {
                dfs(i);
            }
        }
        list.push_back(u);
    });
    for (int u = 0; u < N; ++u) {
        forward(u);
    }
    std::fill(done.begin(), done.end(), false);
    vector<int> comp;
    const auto backward = RecLambda([&](auto&& dfs, const int u) -> void {
        if (done[u]) return;
        done[u] = true;
        for (int i = 0; i < N; ++i) {
            if (edge[i][u]) {
                dfs(i);
            }
        }
        comp.push_back(u);
    });
    vector<int> ord;
    while (!list.empty()) {
        const int u = list.back();
        list.pop_back();
        backward(u);
        for (const int u : comp) {
            for (const int v : comp) {
                reach[u].set(v);
            }
            ord.push_back(u);
        }
        comp.clear();
    }
    for (int i = N - 1; i >= 0; --i) {
        const int u = ord[i];
        for (int j = i + 1; j < N; ++j) {
            const int v = ord[j];
            if (edge[u][v]) {
                reach[u] |= reach[v];
            }
        }
    }
    while (Q--) {
        int a, b;
        std::cin >> a >> b;
        std::cout << (reach[a - 1].test(b - 1) ? "DA" : "NE") << '\n';
    }
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 35 / 35