Submission #1237396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237396		mar	Kutije (COCI21_kutije)	C++20	70 / 70	555 ms	1812 KiB

Main

#include<bits/stdc++.h>
using namespace std;

int n, m, q;
int p[1005], rnk[1005];

int findi(int i) {
    return p[i] == i ? i : p[i] = findi(p[i]);
}

bool same(int i, int j) {
    return findi(i) == findi(j);
}

void unionx(int i, int j) {
    if(same(i, j)) return;
    int x = findi(i), y = findi(j);
    if(rnk[x] > rnk[y]) p[y] = x;
    else {
        p[x] = y;
        if(rnk[x] == rnk[y]) rnk[y]++;
    }
}

int main() {
    cin >> n >> m >> q;
    for(int i = 0; i < n; i++) {
        p[i] = i;
        rnk[i] = 0;
    }

    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            int x;
            cin >> x;
            x--;
            unionx(x, j);
        }
    }

    for(int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        if(same(a, b)) cout << "DA\n";
        else cout << "NE\n";
    }

    return 0;
}

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