제출 #1169424

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169424		DeathIsAwe	Kutije (COCI21_kutije)	C++20	25 / 70	47 ms	1864 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define ll long long
int dsu[1000], ranc[1000];
bool visited[1000];


int leader(int a) {
    if (dsu[a] != a) {
        dsu[a] = leader(dsu[a]);
    }
    return dsu[a];
}


void join(int a, int b) {
    a = leader(a); b = leader(b);
    if (a != b) {
        if (ranc[a] < ranc[b]) {
            dsu[a] = b;
        } else if (ranc[a] > ranc[b]) {
            dsu[b] = a;
        } else {
            dsu[a] = b;
            ranc[b] += 1;
        }
    }
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    for (int i=0;i<1000;i++) {
        dsu[i] = i;
        ranc[i] = 1;
    }


    int n, m, q, d1, d2; cin >> n >> m >> q;
    vector<vector<int>> toyshift(m, vector<int>(n));
    for (int i=0;i<m;i++) {
        for (int j=0;j<n;j++) {
            cin >> d1; d1 -= 1;
            toyshift[i][d1] = j;
        }
    }


    vector<int> cycle;
    int val;
    for (int i=0;i<m;i++) {
        for (int j=0;j<1000;j++) {
            visited[j] = false;
        }


        for (int j=0;j<n;j++) {
            if (visited[j]) continue;
            val = j;
            while (!visited[val]) {
                cycle.pb(val);
                visited[val] = true;
                val = toyshift[i][val];
            }


            for (int k=1;k<cycle.size();k++) {
                join(cycle[0], cycle[k]);
            }
            cycle.clear();
        }
    }


    for (int i=0;i<q;i++) {
        cin >> d1 >> d2;
        d1 -= 1; d2 -= 1;
        if (dsu[d1] == dsu[d2]) {
            cout << "DA" << '\n';
        } else {
            cout << "NE" << '\n';
        }
    } 
}

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