Submission #522986

#	Time	Username	Problem	Language	Result	Execution time	Memory
522986		BadPenalty	Kutije (COCI21_kutije)	C++14	70 / 70	222 ms	9528 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl
const int N = 1e6,mod = 1e9+7;
int dsu[N],s[N];

int root(int x)
{
    while(dsu[x]!=x)
    {
        dsu[x] = dsu[dsu[x]];
        x = dsu[x];
    }
    return x;
}
void onion(int x,int y)
{
    x = root(x);
    y = root(y);
    if(s[x]<s[y])
        swap(x,y);
    dsu[y] = x;
    s[x]+=s[y];
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    for(int i = 1;i<=n;i++)
    {
        dsu[i] = i;
        s[i] = 1;
    }
    for(int l = 0;l<m;l++)
    {
        for(int i = 1;i<=n;i++)
        {
            int a;
            cin>>a;
            onion(i,a);
        }
    }
    while(q--)
    {
        int a,b;
        cin>>a>>b;
        a = root(a);
        b = root(b);
        if(a==b)
            cout<<"DA"<<endl;
        else cout<<"NE"<<endl;
    }
    return 0;
}
/*

*/

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