제출 #1282603

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282603		stefanneagu	Kutije (COCI21_kutije)	C++20	70 / 70	637 ms	4556 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 1001;

struct DSU {
    int root[nmax], sz[nmax];

    void init(int n) {
        for (int i = 1; i <= n; i++) {
            root[i] = i, sz[i] = 1;
        }
    }

    int find(int a) {
        if (root[a] == a) {
            return a;
        }
        return root[a] = find(root[a]);
    }

    void unite(int a, int b) {
        if (a == b) {
            return;
        }
        if (sz[a] > sz[b]) {
            swap(a, b);
        }
        root[a] = b;
        sz[b] += sz[a];
    }
} ds;

int32_t main() {
    int n, m, q;
    cin >> n >> m >> q;
    ds.init(n);
    while (m--) {
        for (int i = 1; i <= n; i++) {
            int a;
            cin >> a;
            ds.unite(ds.find(a), ds.find(i));
        }
    }
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << (ds.find(a) == ds.find(b) ? "DA\n" : "NE\n");
    }
    return 0;
}

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