제출 #1167808

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167808		avighna	Experimental Charges (NOI19_charges)	C++20	100 / 100	14 ms	1420 KiB

charges

#include <bits/stdc++.h>

class UFDS {
public:
  std::vector<int> par;

  UFDS(int n) : par(n + 1) { std::iota(par.begin(), par.end(), 0); }

  int root(int x) { return x == par[x] ? x : par[x] = root(par[x]); }

  void merge(int x, int y) {
    x = root(x), y = root(y);
    if (x == y) {
      return;
    }
    par[y] = x;
  }
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n, q;
  std::cin >> n >> q;
  UFDS dsu(2 * n);
  while (q--) {
    char c;
    std::cin >> c;
    int a, b;
    std::cin >> a >> b;
    if (c == 'A') {
      dsu.merge(a, b + n);
      dsu.merge(a + n, b);
    } else if (c == 'R') {
      dsu.merge(a, b);
      dsu.merge(a + n, b + n);

    } else {
      if (dsu.root(a) == dsu.root(b)) {
        std::cout << "R\n";
      } else if (dsu.root(a) == dsu.root(b + n)) {
        std::cout << "A\n";
      } else {
        std::cout << "?\n";
      }
    }
  }
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 14 / 14
• Subtask 4: 12 / 12
• Subtask 5: 25 / 25
• Subtask 6: 31 / 31