Submission #528352

#	Time	Username	Problem	Language	Result	Execution time	Memory
528352		N1NT3NDO	Kutije (COCI21_kutije)	C++14	70 / 70	211 ms	2512 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

using namespace std;
//using namespace __gnu_pbds;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = 1010;
//bitset<N> bt[N];
int n, q, m, p[N], sz[N];
set<int> se[N];

int f(int x)
{
    return p[x] = (p[x] == x ? x : f(p[x]));
}

void link(int a, int b)
{
    a = f(a); b = f(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    p[b] = a;
    sz[a] += sz[b];
    for(auto u : se[b]) se[a].insert(u);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++)
    {
        p[i] = i;
        se[i].insert(i);
        sz[i] = 1;
    }

    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            int x;
            cin >> x;
            link(j, x);
        }
    }

    while(q--)
    {
        int a, b;
        cin >> a >> b;
        if (se[f(b)].find(a) != se[f(b)].end()) cout << "DA" << '\n';
        else cout << "NE" << '\n';
    }
}

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