QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#482927#6502. Disjoint Set Unionnhuang685WA 164ms3548kbC++203.8kb2024-07-18 03:51:232024-07-18 03:51:23

Judging History

你现在查看的是最新测评结果

  • [2024-07-18 03:51:23]
  • 评测
  • 测评结果:WA
  • 用时:164ms
  • 内存:3548kb
  • [2024-07-18 03:51:23]
  • 提交

answer

/**
 * @author n685
 * @brief
 * @date 2024-07-17
 *
 *
 */
#include <bits/stdc++.h>

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgR(...) 4242
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
void bar() {}
#endif

struct DSU2 {
  std::vector<int> val;
  int cnt{};
  DSU2() = default;
  explicit DSU2(int n) : val(n), cnt(n) {
    for (int i = 0; i < n; ++i) {
      val[i] = i;
    }
  }
  explicit DSU2(const std::vector<int> &val_)
      : val(val_), cnt(static_cast<int>(val_.size())) {}
  int find(int x) {
    if (x == val[x]) {
      return x;
    }
    val[x] = find(val[x]);
    return val[x];
  }
  bool unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) {
      return false;
    }
    val[x] = y;
    cnt--;
    return true;
  }
  bool connected(int u, int v) { return find(u) == find(v); }
  int count() const { return cnt; }
};

struct DSU {
  std::vector<int> val;
  std::vector<std::vector<int>> ch;
  int cnt{};
  DSU() = default;
  explicit DSU(int n) : val(n), ch(n), cnt(n) {
    for (int i = 0; i < n; ++i) {
      val[i] = i;
      ch[i].push_back(i);
    }
  }
  explicit DSU(const std::vector<int> &val_)
      : val(val_), ch(val_.size()), cnt(static_cast<int>(val_.size())) {
    for (int i = 0; i < std::ssize(val); ++i) {
      ch[find(i, false)].push_back(i);
    }
  }
  int find(int x, bool comp = true) {
    if (x == val[x]) {
      return x;
    }
    if (!comp) {
      return find(val[x], comp);
    }
    val[x] = find(val[x], comp);
    return val[x];
  }
  bool unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) {
      return false;
    }
    for (int i : ch[x]) {
      ch[y].push_back(i);
    }
    ch[x].clear();
    val[x] = y;
    cnt--;
    return true;
  }
  bool connected(int u, int v) { return find(u) == find(v); }
  int count() const { return cnt; }
};

struct Query {
  int t{};
  int x{}, y = -1;
};

void solve() {
  int n;
  std::cin >> n;
  std::vector<int> f(n), g(n);
  for (int &v : f) {
    std::cin >> v;
    --v;
  }
  for (int &v : g) {
    std::cin >> v;
    --v;
  }
  DSU2 a(f), b(g);
  std::vector<int> in(n);
  std::vector<std::vector<int>> nxt(n);
  std::vector<std::set<int>> pre(n);
  for (int i = 0; i < n; ++i) {
    int r1 = a.find(i), r2 = g[i];
    if (r1 == r2) {
      continue;
    }
    nxt[r1].push_back(r2);
    ++in[r2];
    pre[r2].insert(r1);
  }
  std::vector<int> t;
  std::queue<int> q;
  for (int i = 0; i < n; ++i) {
    if (in[i] == 0) {
      q.push(i);
    }
  }
  while (!q.empty()) {
    int node = q.front();
    q.pop();
    t.push_back(node);
    for (int i : nxt[node]) {
      if (--in[i] == 0) {
        q.push(i);
      }
    }
  }
  if (std::ssize(t) != n) {
    std::cout << "NO\n";
    return;
  }
  DSU dsu(f);
  std::vector<Query> ans;
  auto find = [&](int x) {
    ans.emplace_back(1, x);
    dsu.find(x);
  };
  auto unite = [&](int x, int y) {
    ans.emplace_back(2, x, y);
    dsu.unite(x, y);
  };
  for (int i : t) {
    for (int j : pre[i]) {
      unite(dsu.find(j, false), i);
    }
    for (int j : dsu.ch[i]) {
      if (dsu.val[j] != g[j]) {
        find(j);
      }
    }
  }

  if (dsu.val != g) {
    std::cout << "NO\n";
    return;
  }
  std::cout << "YES\n";
  std::cout << ans.size() << '\n';
  for (auto [tt, x, y] : ans) {
    if (tt == 1) {
      std::cout << tt << ' ' << x + 1 << '\n';
    } else {
      std::cout << tt << ' ' << x + 1 << ' ' << y + 1 << '\n';
    }
  }
}

int main() {
#ifndef LOCAL
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
#endif

  int t;
  std::cin >> t;
  for (int i = 0; i < t; ++i) {
    dbg(i + 1);
    solve();
    bar();
  }
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3544kb

input:

5
3
1 2 3
2 2 3
4
1 2 3 3
1 1 1 2
5
1 2 3 4 5
2 3 4 5 5
5
1 1 1 1 1
1 2 3 4 5
6
1 2 2 4 5 6
1 1 5 1 4 2

output:

YES
2
1 1
2 1 2
YES
9
1 3
1 4
2 3 2
1 2
1 3
1 4
2 2 1
2 1 1
1 3
YES
8
1 1
2 1 2
1 2
2 2 3
1 3
2 3 4
1 4
2 4 5
NO
YES
14
1 6
2 6 2
1 2
1 3
2 2 5
1 5
1 2
1 3
2 5 4
1 4
1 2
2 4 1
2 1 1
1 2

result:

ok good! (YES count = 4, NO count = 1) (5 test cases)

Test #2:

score: -100
Wrong Answer
time: 164ms
memory: 3548kb

input:

100000
5
1 2 1 1 1
2 2 1 1 2
5
3 2 3 4 1
3 2 3 4 1
5
1 2 3 4 3
1 4 4 1 1
5
1 2 3 5 3
1 2 2 5 2
5
5 2 3 5 5
5 2 3 5 5
5
1 2 3 4 5
5 3 3 4 5
5
1 2 3 4 5
1 4 1 4 4
5
1 2 3 1 5
1 2 3 1 2
5
1 2 3 3 1
1 3 3 3 1
5
1 2 3 4 3
2 2 4 4 4
5
1 2 2 4 5
5 2 2 4 5
5
1 2 1 4 5
5 2 5 5 5
5
1 2 3 4 5
1 2 5 5 1
5
1 4 3...

output:

YES
4
1 1
1 5
2 1 2
1 5
YES
1
2 3 1
YES
10
1 2
1 3
1 5
2 2 4
2 3 4
1 4
1 5
2 4 1
2 1 1
1 5
YES
5
1 3
1 5
2 3 5
2 3 2
1 5
YES
0
YES
4
1 1
1 2
2 1 5
2 2 3
YES
6
1 2
1 3
1 5
2 3 1
2 2 4
2 5 4
YES
2
1 5
2 5 2
YES
2
1 2
2 2 3
YES
6
1 1
1 3
1 5
2 1 2
2 3 4
1 5
YES
2
1 1
2 1 5
YES
6
1 1
1 3
1 4
2 1 5
2 4 5...

result:

wrong answer you didn't find a solution but jury did (test case 87)