Submission #588422

#	Time	Username	Problem	Language	Result	Execution time	Memory
588422		MilosMilutinovic	Kutije (COCI21_kutije)	C++14	70 / 70	161 ms	9464 KiB

Main

/**
 *    author:  wxhtzdy
 *    created: 03.07.2022 11:16:52
**/
#include <bits/stdc++.h>

using namespace std;

class dsu {
  public:
  vector<int> p;
  int n;
  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }
  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }
  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      return true;
    }
    return false;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, m, q;
  cin >> n >> m >> q;
  dsu d(n);
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      int x;
      cin >> x;
      --x;
      d.unite(j, x);
    }
  }
  while (q--) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    cout << (d.get(a) == d.get(b) ? "DA" : "NE") << '\n';
  }                                                    
  return 0;
}

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