제출 #1108758

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1108758		huantran	Kutije (COCI21_kutije)	C++17	70 / 70	221 ms	27464 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long int;
const int maxn = 5e5 + 5;
const int oo = 1e9 + 7;
const ll inf = 1e18;

int n, m, q;
vector<int> adj[maxn];
int comp[maxn], cnt = 0;

void dfs(int u) {
    comp[u] = cnt;

    for (auto j : adj[u]) {
        if (comp[j])
            continue;
        dfs(j);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int u;
            cin >> u;
            adj[u].push_back(j);
        }
    }

    for (int i = 1; i <= n; i++) {
        if (!comp[i]) {
            ++cnt;
            dfs(i);
        }
    }

    while (q--) {
        int u, v;
        cin >> u >> v;
        if (comp[u] == comp[v])
            cout << "DA" << '\n';
        else
            cout << "NE" << '\n';
    }
}

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