QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#109157#6502. Disjoint Set UnionmagicduckWA 128ms3460kbC++143.1kb2023-05-27 17:09:042023-05-27 17:09:07

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-27 17:09:07]
  • 评测
  • 测评结果:WA
  • 用时:128ms
  • 内存:3460kb
  • [2023-05-27 17:09:04]
  • 提交

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;
}

详细

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)