QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#143090#6502. Disjoint Set UnionqzezWA 125ms3748kbC++141.8kb2023-08-20 16:06:382023-08-20 16:06:39

Judging History

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

  • [2023-08-20 16:06:39]
  • 评测
  • 测评结果:WA
  • 用时:125ms
  • 内存:3748kb
  • [2023-08-20 16:06:38]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
const int N=1e3+10;
int T,n,fa[N],a[N],vis[N];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
vector<tuple<int,int,int> >ans;
void merge(int x,int y){
	ans.push_back({2,x,y});
	x=find(x),y=find(y);
	if(x^y)fa[x]=y;
}
vector<int>to[N];
void dfs(int u){
	for(int v:to[u]){
		dfs(v);
	}
	if(fa[u]==u)for(int v:to[u]){
		merge(v,u);
	}
	if(fa[u]==u)for(int v:to[u]){
		find(v);
		ans.push_back({1,v,0});
	}
	// if(u==1){
		// debug(u,ary(fa,1,n));
	// }
}
bool get(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&fa[i]);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]^i)to[a[i]].push_back(i);
	}
	fill(vis,vis+1+n,0);
	for(int i=1;i<=n;i++)if(a[i]^i){
		vis[i]=1;
		for(int j=a[i];;j=a[j]){
			if(j==i)return 0;
			if(vis[j])break;
			vis[j]=1;
			if(a[j]==j)break;
		}
	}
	ans.clear();
	for(int i=1;i<=n;i++)if(a[i]==i)dfs(i);
	// debug(ary(fa,1,n),ary(a,1,n));
	for(int i=1;i<=n;i++)if(fa[i]^a[i])return 0;
	puts("YES");
	printf("%d\n",(int)ans.size());
	for(auto x:ans){
		if(get<0>(x)==1)printf("%d %d\n",get<0>(x),get<1>(x));
		else printf("%d %d %d\n",get<0>(x),get<1>(x),get<2>(x));
	}
	return 1;
}
void clr(){
	for(int i=1;i<=n;i++)to[i].clear();
}
int main(){
	for(scanf("%d",&T);T--;clr())if(!get())puts("NO");
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3684kb

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
2 1 2
1 1
YES
6
2 4 2
1 4
2 2 1
2 3 1
1 2
1 3
YES
8
2 1 2
1 1
2 2 3
1 2
2 3 4
1 3
2 4 5
1 4
NO
YES
10
2 6 2
1 6
2 3 5
1 3
2 5 4
1 5
2 2 1
2 4 1
1 2
1 4

result:

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

Test #2:

score: -100
Wrong Answer
time: 125ms
memory: 3748kb

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
8
2 3 1
2 4 1
1 3
1 4
2 1 2
2 5 2
1 1
1 5
YES
2
2 1 3
1 1
NO
YES
4
2 3 2
2 5 2
1 3
1 5
YES
4
2 1 5
2 4 5
1 1
1 4
YES
4
2 2 3
1 2
2 1 5
1 1
YES
6
2 3 1
1 3
2 2 4
2 5 4
1 2
1 5
YES
4
2 4 1
1 4
2 5 2
1 5
YES
6
2 5 1
1 5
2 2 3
2 4 3
1 2
1 4
YES
6
2 1 2
1 1
2 3 4
2 5 4
1 3
1 5
YES
4
2 3 2
1 3
2 1 5
1...

result:

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