제출 #996504

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
996504		ISherozia321	Kutije (COCI21_kutije)	C++14	70 / 70	647 ms	9548 KiB

Main

#include <bits/stdc++.h>
using namespace std;
# define pb push_back
# define int long long
int n, m, q;
const int N = 1100;
int parent[N];
int depth[N];
int a[N];
int find_set(int a){
    if (parent[a] == a){
        return a;
    }
    return parent[a] = find_set(parent[a]);
}
void merge_set(int a, int b){
    a = find_set(a);
    b = find_set(b);
    if (a == b){
        return;
    }
    if (depth[a] < depth[b]){
        swap(a, b);
    }
    parent[b] = a;
    if (depth[a] == depth[b]){
        depth[a]++;
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> q;
    for (int i= 0; i < N; i++){
        parent[i] = i;
    }
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n; j++){
            cin >> a[j];
            merge_set(a[j], j);
        }
    }
    while (q--){
        int x, y;
        cin >> x >> y;
        if (find_set(x) == find_set(y)){
            cout << "DA" << endl;
        }
        else{
            cout << "NE" << endl;
        }
    }
}

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