Submission #745179

#	Time	Username	Problem	Language	Result	Execution time	Memory
745179		Ahmed57	Kutije (COCI21_kutije)	C++17	70 / 70	967 ms	9608 KiB

Main

//LCA
#include <bits/stdc++.h>

using namespace std;
//DSU
int pr[1001];
int gs[1001];

int findleader(int x){
    if(pr[x]==x){
        return x;
    }
    return pr[x] = findleader(pr[x]);
}
bool samegroup(int x,int y){
    int led1 = findleader(x);
    int led2 = findleader(y);
    return led1==led2;
}
void mergegroup(int x,int y){
    int led1 = findleader(x);
    int led2 = findleader(y);
    if(led1==led2)return;
    if(gs[led1]>gs[led2]){
        pr[led2]=led1;
        gs[led1]+=gs[led2];
    }else{
        pr[led1]=led2;
        gs[led2]+=gs[led1];
    }
}
int get(int x){
    int led = findleader(x);
    return gs[led];
}
int main(){
    int n,m,q;
    cin>>n>>m>>q;
    for(int i = 0;i<=n;i++)pr[i] = i , gs[i] = 1;
    for(int i = 0;i<m;i++){
        for(int j = 1;j<=n;j++){
            int x;cin>>x;
            mergegroup(x,j);
        }
    }
    while(q--){
        int a,b;cin>>a>>b;
        if(samegroup(a,b))cout<<"DA\n";
        else cout<<"NE\n";
    }
}

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