QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#116388#6502. Disjoint Set UnionlxhcrTL 2ms3460kbC++142.2kb2023-06-28 17:35:162023-06-28 17:35:16

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-28 17:35:16]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:3460kb
  • [2023-06-28 17:35:16]
  • 提交

answer

#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i) 
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
using namespace std;

const int maxn=1e3+10;

int n;
vector<int>E[maxn];
int F[maxn],G[maxn],deg[maxn];
vector<tuple<int,int,int>>Ans;

struct UN{
	int f[maxn];
	int Find(int x){ return f[x]==x ? x : f[x]=Find(f[x]); }
	void Merge(int x,int y){ x=Find(x),y=Find(y);f[x]=y; }
}A,B;

bool Check(int *G){ Rep(i,1,n){ int u=i,cnt=0; while(u!=G[u]){ u=G[u];++cnt; if(u==i || cnt>=n)return false; } } return true; }

bool Check2(){ set<int>S;Rep(i,1,n)S.insert(F[i]); Rep(i,1,n)if(!S.count(G[i]))return false; return true; }

void solve(){
	cin>>n;Ans.resize(0);Rep(i,1,n)cin>>F[i],A.f[i]=F[i];Rep(i,1,n)cin>>G[i],B.f[i]=G[i],deg[i]=0;
	if(!Check(F) || (!Check(G)) || (!Check2()))return cout<<"NO\n",void();
	Rep(i,1,n)Rep(j,i+1,n)if((A.Find(i)==A.Find(j)) && (B.Find(i)!=B.Find(j)))return cout<<"NO\n",void();
	Rep(i,1,n)A.f[i]=F[i];Rep(i,1,n)E[i].resize(0);
	Rep(i,1,n)if(A.Find(G[i])!=A.Find(i))E[A.Find(i)].emplace_back(A.Find(G[i])),++deg[A.Find(G[i])];
	queue<int>q;vector<int>vec;int cnt1=0;Rep(i,1,n)A.f[i]=F[i];
	Rep(i,1,n)if(F[i]==i){ ++cnt1;if(!deg[i])q.emplace(i); }
	while(!q.empty()){
		int u=q.front();q.pop();vec.emplace_back(u);
		for(auto v : E[u])(!(--deg[v])) && (q.emplace(v),0);
	}if(vec.size()!=cnt1)return cout<<"NO\n",void();
	Rep(i,1,n)if(F[i]!=G[i])A.Find(i),Ans.emplace_back(1,i,0);
	for(int i=1;i<vec.size();++i)for(int j=i-1;j>=0;--j)if(B.Find(vec[j])==B.Find(vec[i])){
		Ans.emplace_back(2,vec[j],vec[i]);A.Merge(vec[j],vec[i]);
		Rep(i,1,n)if(A.f[i]!=G[i]){ Ans.emplace_back(1,i,0);A.Find(i); }
		break;
	}
	Rep(i,1,n)if(A.f[i]!=G[i])return cout<<"NO\n",void();
	cout<<"YES\n";cout<<Ans.size()<<"\n";
	for(auto it : Ans)if(get<0>(it)==1)cout<<1<<" "<<get<1>(it)<<"\n";else cout<<2<<" "<<get<1>(it)<<" "<<get<2>(it)<<"\n";
	Rep(i,1,n)cerr<<A.f[i]<<" ";
}

int tex;
int main (){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>tex;while(tex--)solve(); }

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
2
1 1
2 1 2
YES
9
1 2
1 3
1 4
2 3 2
1 2
1 3
1 4
2 2 1
1 3
YES
14
1 1
1 2
1 3
1 4
2 1 2
1 2
1 3
1 4
2 2 3
1 3
1 4
2 3 4
1 4
2 4 5
NO
YES
20
1 2
1 3
1 4
1 5
1 6
2 6 2
1 2
1 3
1 4
1 5
2 2 5
1 2
1 3
1 4
1 5
2 5 4
1 2
1 4
2 4 1
1 2

result:

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

Test #2:

score: -100
Time Limit Exceeded

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
0
YES
15
1 2
1 3
1 4
1 5
2 2 3
1 2
1 3
1 4
1 5
2 3 4
1 2
1 4
1 5
2 4 1
1 5
YES
4
1 3
1 5
2 3 2
1 5
YES
0
YES
5
1 1
1 2
2 1 5
1 2
2 2 3
YES
12
1 2
1 3
1 5
2 2 5
1 2
1 3
1 5
2 3 1
1 2
1 5
2 5 4
1 2
YES
2
1 5
2 5 2
YES
2
1 2
2 2 3
YES
8
1 1
1 3
1 5
2 1 2
1 3
1 5
2 3 4
1 5
YE...

result: