Submission #577344

#	Time	Username	Problem	Language	Result	Execution time	Memory
577344		Alexandruabcde	Kutije (COCI21_kutije)	C++14	70 / 70	170 ms	18384 KiB

Main

#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 1005;

int N, M, Q;

vector <int> G[NMAX];
int comp[NMAX];
int nr;

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M >> Q;

    for (int i = 1; i <= M; ++ i ) {
        for (int j = 1; j <= N; ++ j ) {
            int x;
            cin >> x;

            G[j].push_back(x);
            G[x].push_back(j);
        }
    }
}

void Dfs (int nod) {
    comp[nod] = nr;

    for (auto it : G[nod]) {
        if (comp[it] != 0) continue;

        Dfs(it);
    }
}

void Precompute () {
    for (int i = 1; i <= N; ++ i ) {
        if (comp[i] == 0) {
            ++ nr;
            Dfs(i);
        }
    }
}

void Solve () {
    for (int i = 1; i <= Q; ++ i ) {
        int x, y;
        cin >> x >> y;

        cout << (comp[x] == comp[y] ? "DA\n" : "NE\n");
    }
}

int main () {
    Read();
    Precompute();
    Solve();

    return 0;
}

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