QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#109157 | #6502. Disjoint Set Union | magicduck | WA | 128ms | 3460kb | C++14 | 3.1kb | 2023-05-27 17:09:04 | 2023-05-27 17:09:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
template<typename T> inline void read(T &F) {
F = 0; int R = 1; char CH = getchar();
for(; !isdigit(CH); CH = getchar()) if(CH == '-') R = -1;
for(; isdigit(CH); CH = getchar()) F = F * 10 + CH - 48;
F *= R;
}
const int N = 1e3 + 10;
int f[N], g[N], n, flag[N];
vector<pair<int, pair<int, int> > > R;
int findx(int x) {
return f[x] == x ? x : f[x] = findx(f[x]);
}
void find(int x) {
findx(x); R.emplace_back(make_pair(1, make_pair(x, 0)));
}
void unite(int x, int y) {
x = findx(x), y = findx(y);
f[x] = y; R.emplace_back(make_pair(2, make_pair(x, y)));
}
int vis[N], d[N], dep[N], id[N]; vector<int> edge[N];
bool check() {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) vis[j] = 0;
int x = i;
while(g[x] != x) {
if(vis[x]) return false;
vis[x] = 1; x = g[x];
}
}
return true;
}
void build() {
for(int i = 1; i <= n; i++) vis[i] = d[i] = 0, id[i] = i;
sort(id + 1, id + n + 1, [&](int x, int y) {return dep[x] > dep[y];});
for(int i = 1; i <= n; i++) {
int x = id[i];
if(g[x] == x) continue;
if(flag[x] && g[x] != f[x] && !vis[f[x]]) vis[f[x]] = g[x], d[g[x]]++;//, cerr << x << ' ' << f[x] << ' ' << vis[f[x]] << endl;
if(f[x] == x && !vis[x]) vis[x] = g[x], d[g[x]]++;//, cerr << "??" << x << ' ' << vis[x] << endl;
}
queue<int> q;
for(int i = 1; i <= n; i++)
if(d[i] == 0) q.push(i);
while(!q.empty()) {
int x = q.front(); q.pop();
if(!vis[x]) continue; assert(!flag[x] && !flag[g[x]]);
unite(x, vis[x]);
for(int i = 1; i <= n; i++)
if(f[i] == x && g[i] != x) find(i);
d[vis[x]]--;
if(!d[vis[x]]) q.push(vis[x]);
}
}
void dfs(int x) {
for(int i : edge[x])
dep[i] = dep[x] + 1, dfs(i);
}
int main() {
//freopen("path.in", "r", stdin);
//freopen("path.out", "w", stdout);
int T; read(T);
while(T--) {
read(n); R.clear();
for(int i = 1; i <= n; i++) read(f[i]);
for(int i = 1; i <= n; i++) read(g[i]);
if(!check()) {
puts("NO"); continue;
}
for(int i = 1; i <= n; i++) {
flag[i] = 0;
if(f[i] == i) continue;
if(g[i] != f[i] || f[f[i]] == f[i]) flag[i] = 1;
}
int F = 1;
for(int i = 1; i <= n && F; i++) {
if(!flag[i]) continue;
int x = i;
while(f[x] != x) {
F &= flag[x];
x = f[x];
}
}
if(!F) {
puts("NO"); continue;
}
for(int i = 1; i <= n; i++) if(flag[i]) find(i);
for(int i = 1; i <= n && F; i++)
if(g[i] != i) {
if(flag[i] && flag[g[i]]) F = 0;
}
else if(f[i] != i) F = 0;
if(!F) {
puts("NO"); continue;
}
for(int i = 1; i <= n; i++) edge[i].clear();
for(int i = 1; i <= n; i++) if(g[i] != i) edge[g[i]].emplace_back(i);
for(int i = 1; i <= n; i++)
if(g[i] == i) {
dep[i] = 0, dfs(i);
}
build();
for(int i = 1; i <= n && F; i++)
if(f[i] != g[i]) F = 0;
if(!F) {
puts("NO"); continue;
}
puts("YES");
cout << R.size() << '\n';
for(auto i : R) {
if(i.first == 1) cout << i.first << ' ' << i.second.first << '\n';
else cout << i.first << ' ' << i.second.first << ' ' << i.second.second << '\n';
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3460kb
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 1 2 1 2 YES 5 1 4 2 3 2 1 4 2 2 1 1 3 YES 4 2 1 2 2 2 3 2 3 4 2 4 5 NO YES 8 1 3 2 6 2 2 2 5 1 3 2 5 4 1 2 2 4 1 1 2
result:
ok good! (YES count = 4, NO count = 1) (5 test cases)
Test #2:
score: -100
Wrong Answer
time: 128ms
memory: 3412kb
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 5 1 3 1 4 1 5 2 1 2 1 5 YES 1 1 1 YES 6 1 5 2 2 4 2 3 4 1 5 2 4 1 1 5 YES 3 1 5 2 3 2 1 5 YES 2 1 1 1 4 YES 2 2 1 5 2 2 3 YES 3 2 2 4 2 3 1 2 5 4 YES 2 1 4 2 5 2 YES 3 1 4 1 5 2 2 3 YES 4 1 5 2 1 2 2 3 4 1 5 YES 2 1 3 2 1 5 YES 4 1 3 2 1 5 1 3 2 4 5 YES 3 2 3 5 2 4 5 2 5 1 YES 7 1 2 1 5 2 4 3 1 ...
result:
wrong answer you didn't find a solution but jury did (test case 5184)