QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#373645#6502. Disjoint Set Union514imbaWA 1ms3824kbC++112.9kb2024-04-01 21:20:352024-04-01 21:20:37

Judging History

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

  • [2024-04-01 21:20:37]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3824kb
  • [2024-04-01 21:20:35]
  • 提交

answer

#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define MP make_pair
using namespace std;
typedef long long ll;
template<typename T> void read( T &r ) {
	r=0; bool w=false; char ch=getchar();
	while( ch < '0' || ch > '9' ) w = !(ch^45), ch = getchar();
	while( ch >= '0' && ch <= '9' ) r = (r<<1) + (r<<3) + (ch^48), ch = getchar();
	r = w ? -r : r;
}

#define MAXN 1000
int n, fsonvis[MAXN+5], f[MAXN+5], g[MAXN+5], frt[MAXN+5];
int fa[2][MAXN+5], in[MAXN+5];
vector<int> to[MAXN+5];
int find( int x, int idx = 0 ) {
	if( fa[idx][x] == x ) return x;
	return fa[idx][x] = find(fa[idx][x],idx);
}
void unite( int x , int y, int idx = 0 ) {
	x = find(x,idx), y = find(y,idx);
	fa[idx][x] = y;
}
void add( int u , int v ) {
	++in[v]; to[u].pb(v);
}
queue<int> q; int arr[MAXN+5];
int st[2][MAXN+5];vector<int> cl[MAXN+5];
struct ansNode{
	int x, y;
}ans[MAXN*MAXN*2+5];int anstot;
bool topo( int rt ){
	while( !q.empty() ) q.pop(); arr[0] = 0;
	for(int i=1;i<=n;i++) if( find(i,1) == rt && !in[i] && frt[i] ) q.push(i);
	while( !q.empty() ) {
		int u = q.front(); q.pop(); arr[++arr[0]] = u;
		for(auto v: to[u]) if( --in[v] == 0 ) q.push(v);
	}
	for(int i=1;i<=n;i++) if( find(i,1) == rt && in[i] ) return false;
	#define st1 st[x]
	#define st2 st[x^1]
	int x = 0; st2[0] = 0; 
	st1[st1[0]=1]=arr[1]; for(auto i: cl[arr[1]]) st1[++st1[0]] = i;
	x^=1;
	for(int i=2;i<=arr[0];i++) {
		st1[st1[0]=1] = arr[i];
		for(auto v: cl[arr[i]]) st1[++st1[0]] = v;
		for(int j=1;j<=st2[0];j++) {
			ans[++anstot] = {st2[j], arr[i]};
			if( g[st2[j]] != arr[i] ) st1[++st1[0]] = st2[j];
		}
		x^=1;
	}
	return true;
}
int topovis[MAXN+5];
void solve() {
	read(n); anstot = 0;
	for(int i=1;i<=n;i++) fa[0][i] = fa[1][i] = i, to[i].clear(), cl[i].clear(), 
	fsonvis[i] = false, frt[i] = false, in[i]=0, topovis[i]=false;
	for(int i=1;i<=n;i++) read(f[i]), unite(i,f[i]), fsonvis[f[i]] = true;
	for(int i=1;i<=n;i++) if( find(i) == i ) frt[i] = true;
	for(int i=1;i<=n;i++) { 
		read(g[i]); 
		if( f[i] != g[i] && !frt[g[i]] ) { puts("NO"); return; } 
		if( find(i) != find(g[i]) ) add(find(i),g[i]);
		unite(i,g[i],1);
	}
	for(int i=1;i<=n;i++) {
		if( find(i,1) != find(f[i],1) ) { puts("NO"); return; }
		if( !fsonvis[i] && !frt[i] ) {
			bool chg = false;
			for(int p=i;!frt[p];p=f[p]) {
				if( f[p] != g[p] ) {
					chg = true;
					if( !frt[f[p]] ) ans[++anstot] = { p, find(p,0) };
					cl[find(p)].pb(p);
				}
				else if( chg && !frt[f[p]] ) { puts("NO"); return; }
			}
		}
	}
	
	for(int i=1;i<=n;i++) {
		if( !topovis[find(i,1)] ) {
			if( !topo(find(i,1)) ) { puts("NO"); return; }
			topovis[find(i,1)] = true;
		}
	}
	puts("YES"); printf("%d\n",anstot);
	for(int i=1;i<=anstot;i++) printf("2 %d %d\n",ans[i].x, ans[i].y);
}
int t;
int main() {
	read(t);
	while( t-- ) solve();
	return 0;
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3824kb

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

result:

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