QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#482927 | #6502. Disjoint Set Union | nhuang685 | WA | 164ms | 3548kb | C++20 | 3.8kb | 2024-07-18 03:51:23 | 2024-07-18 03:51:23 |
Judging History
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();
}
}
Details
Tip: Click on the bar to expand more detailed information
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)