QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#116388 | #6502. Disjoint Set Union | lxhcr | TL | 2ms | 3460kb | C++14 | 2.2kb | 2023-06-28 17:35:16 | 2023-06-28 17:35:16 |
Judging History
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...