Submission #26928018

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <tuple>

int main() {
  int64_t N, Q;
  std::cin >> N >> Q;
  std::vector<std::tuple<int64_t, int64_t, int64_t>> query(Q);
  for (int64_t i = 0; i < Q; i++) {
    int64_t t;
    std::cin >> t;
    if (t == 1) {
      int64_t x = 0;
      int64_t y = 0;
      std::cin >> x >> y;
      query.at(i) = std::make_tuple(t, x - 1, y - 1);
    } else if (t == 2) {
      int64_t x = 0;
      int64_t y = 0;
      std::cin >> x >> y;
      query.at(i) = std::make_tuple(t, x - 1, y - 1);
    } else if (t == 3) {
      int64_t x = 0;
      std::cin >> x;
      query.at(i) = std::make_tuple(t, x - 1, -1);
    }
  }

  std::vector<std::vector<int64_t>> connection(N, std::vector<int64_t>(3, -1));
  for (int64_t i = 0; i < N; i++) {
    connection.at(i).at(0) = i;
  }
  for (auto q : query) {
    int64_t t = std::get<0>(q);
    int64_t x = std::get<1>(q);
    int64_t y = std::get<2>(q);

    if (t == 1) {
      connection.at(x).at(2) = y;
      connection.at(y).at(0) = connection.at(x).at(0);
      connection.at(y).at(1) = x;

      int64_t z = connection.at(y).at(2);
      while (z != -1) {
        connection.at(z).at(0) = connection.at(x).at(0);
        z = connection.at(z).at(2);
      }
    } else if (t == 2) {
      connection.at(x).at(2) = -1;
      connection.at(y).at(1) = -1;
      connection.at(y).at(0) = y;
      int64_t z = connection.at(y).at(2);
      while (z != -1) {
        connection.at(z).at(0) = y;
        z = connection.at(z).at(2);
      }
    } else if (t == 3) {
      int64_t z = x;
      z = connection.at(z).at(0);

      std::vector<int64_t> connected;
      while (z != -1) {
        connected.push_back(z + 1);
        z = connection.at(z).at(2);
      }
      std::cout << connected.size() << " ";
      for (size_t i = 0; i < connected.size(); i++) {
        if (i) std::cout << " ";
        std::cout << connected.at(i);
      }
      std::cout << std::endl;
    }
  }

  return 0;
}

Submission Info

Judge Result