QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#111539#6502. Disjoint Set UnionAFewSunsWA 88ms3756kbC++142.9kb2023-06-07 15:41:102023-06-07 15:41:11

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-07 15:41:11]
  • 评测
  • 测评结果:WA
  • 用时:88ms
  • 内存:3756kb
  • [2023-06-07 15:41:10]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
namespace my_std{
	#define ll long long
	#define bl bool
	ll my_pow(ll a,ll b,ll mod){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res=(res*a)%mod;
			a=(a*a)%mod;
			b>>=1;
		}
		return res;
	}
	ll qpow(ll a,ll b){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res*=a;
			a*=a;
			b>>=1;
		}
		return res;
	}
	#define db double
	#define pf printf
	#define pc putchar
	#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
	#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
	#define go(u) for(ll i=head[u];i;i=e[i].nxt)
	#define enter pc('\n')
	#define space pc(' ')
	#define fir first
	#define sec second
	#define MP make_pair
	#define il inline
	#define inf 8e18
	#define random(x) rand()*rand()%(x)
	#define inv(a,mod) my_pow((a),(mod-2),(mod))
	il ll read(){
		ll sum=0,f=1;
		char ch=0;
		while(!isdigit(ch)){
			if(ch=='-') f=-1;
			ch=getchar();
		}
		while(isdigit(ch)){
			sum=sum*10+(ch^48);
			ch=getchar();
		}
		return sum*f;
	}
	il void write(ll x){
		if(x<0){
			x=-x;
			pc('-');
		}
		if(x>9) write(x/10);
		pc(x%10+'0');
	}
	il void writeln(ll x){
		write(x);
		enter;
	}
	il void writesp(ll x){
		write(x);
		space;
	}
}
using namespace my_std;
vector<ll> vec[1010];
vector<pair<ll,pair<ll,ll> > > ans;
ll t,n,fa[1010],g[1010],rt[1010],cnt=0,d[1010],dfn[1010],tot=0,mp[1010];
bl ck[1010];
ll find(ll x){
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
il void topo(){
	queue<ll> q;
	fr(i,1,cnt) if(!d[rt[i]]) q.push(rt[i]);
	while(!q.empty()){
		ll u=q.front();
		q.pop();
		dfn[++tot]=u;
		mp[u]=tot;
		fr(i,0,(ll)vec[u].size()-1){
			ll v=vec[u][i];
			d[v]--;
			if(!d[v]) q.push(v);
		}
	}
}
il void clr(){
	fr(i,1,n) vec[i].clear();
	fr(i,1,n) d[i]=ck[i]=0;
	cnt=tot=0;
	ans.clear();
}
int main(){
	t=read();
	while(t--){
		n=read();
		fr(i,1,n) fa[i]=read();
		fr(i,1,n) g[i]=read(); 
		fr(i,1,n){
			if(fa[i]==i){
				rt[++cnt]=i;
				ck[i]=1;
			}
		}
		bl pd=0;
		fr(i,1,n){
			if(fa[i]!=g[i]){
				find(i);
				ans.push_back(MP(1,MP(i,0)));
				if(!ck[g[i]]) pd=1;
				else{
					vec[g[i]].push_back(fa[i]);
					d[fa[i]]++;
				}
			}
		}
		topo();
		if(cnt!=tot||pd){
			pf("NO\n");
			clr();
			continue;
		}
		pfr(i,tot,2){
			ll maxx=-inf;
			fr(j,1,n) if(fa[j]==dfn[i]&&fa[j]!=g[j]) maxx=max(maxx,mp[g[j]]);
			if(maxx!=-inf){
				fa[dfn[i]]=dfn[maxx];
				ans.push_back(MP(2,MP(dfn[i],dfn[maxx])));
			}
			fr(j,1,n){
				if(fa[j]!=g[j]){
					find(j);
					ans.push_back(MP(1,MP(j,0)));
				}
			}
		}
		fr(i,1,n) if(fa[i]!=g[i]) pd=1;
		if(pd){
			pf("NO\n");
			clr();
			continue;
		}
		pf("YES\n");
		writeln(ans.size());
		fr(i,0,(ll)ans.size()-1){
			if(ans[i].fir==1) pf("1 %lld\n",ans[i].sec.fir);
			else pf("2 %lld %lld\n",ans[i].sec.fir,ans[i].sec.sec);
		}
		clr();
	}
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3648kb

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
Wrong Answer
time: 88ms
memory: 3756kb

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

result:

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