Submission #504140

#	Time	Username	Problem	Language	Result	Execution time	Memory
504140		Hacv16	Kutije (COCI21_kutije)	C++17	70 / 70	221 ms	9240 KiB

Main

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

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

#define endl '\n'
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define bn binary_search
#define lb lower_bound
#define up upper_bound
#define np next_permutation
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define mdc(x, y) __gcd(x, y)
#define dbg(x) cout << #x << ": " << "[ " << x << " ]\n"

typedef int ii;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef priority_queue<int, vector<int>, greater<int>> heap;

const int MAX = 2e6 + 15;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const int VAR[4] = {-1, 1, 0, 0};

struct DSU{
    vector<int> sze, id;

    DSU(int n) : sze(n, 1), id(n){
        iota(id.begin(), id.end(), 0);
    }

    int find(int v){
        if(id[v] == v)
            return v;

        return id[v] = find(id[v]);
    }

    void join(int u, int v){
        u = find(u), v = find(v);
        if(u == v) return;
        if(sze[u] > sze[v]) swap(u, v);
        id[u] = v, sze[v] += sze[u];
    }

    bool same(int u, int v){
        return (find(u) == find(v));
    }
};

int n, m, q;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m >> q;

    DSU toys(n + 1);

    while(m--){
        for(int i = 1; i <= n; i++){
            int a; cin >> a;
            toys.join(i, a);
        }
    }

    while(q--){
        int u, v; cin >> u >> v;
        cout << ((toys.same(u, v)) ? "DA" : "NE") << '\n';
    }
    
    return 0;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
    * brute force to find pattern?
    * sort?
    * graph?
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

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