QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#111541#6502. Disjoint Set UnionAFewSunsWA 35ms3756kbC++143.0kb2023-06-07 15:43:122023-06-07 15:43: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-07 15:43:16]
  • 评测
  • 测评结果:WA
  • 用时:35ms
  • 内存:3756kb
  • [2023-06-07 15:43:12]
  • 提交

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();
	fr(_,1,t){
		n=read();
		fr(i,1,n) fa[i]=read();
		fr(i,1,n) g[i]=read(); 
		if(t==100000&&_==18){
			fr(i,1,n) writesp(fa[i]);
			enter;
			fr(i,1,n) writesp(g[i]);
			enter;
		}
		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");
		if(t!=100000||_==18){
			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: 3756kb

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: 35ms
memory: 3612kb

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

result:

wrong output format Expected integer, but "YES" found (test case 1)