QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#143087 | #6502. Disjoint Set Union | qzez | WA | 111ms | 3744kb | C++14 | 1.8kb | 2023-08-20 15:55:51 | 2023-08-20 15:55:52 |
Judging History
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);
}
for(int v:to[u]){
merge(v,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: 3636kb
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: 111ms
memory: 3744kb
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 NO NO NO 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 1 YES 6 2 1 5 2 3 5 2 4 5 1 1 1 3 1...
result:
wrong answer you didn't find a solution but jury did (test case 2)