QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#373870#6502. Disjoint Set Union514imbaWA 72ms4176kbC++113.0kb2024-04-02 09:32:142024-04-02 09:32:16

Judging History

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

  • [2024-04-02 09:32:16]
  • 评测
  • 测评结果:WA
  • 用时:72ms
  • 内存:4176kb
  • [2024-04-02 09:32:14]
  • 提交

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; st1[0] = st2[0] = 0;
	for(auto i: cl[arr[1]]) st1[++st1[0]] = i;
	#define FOR(i,a,b) for(int i=a;i<=b;i++)
	FOR(i,2,arr[0]) {
		st2[0] = 0;
		ans[++anstot] = {arr[i-1],arr[i]}; if( g[arr[i-1]] != arr[i] ) st2[++st2[0]] = arr[i-1];
		FOR(j,1,st1[0]) {
			ans[++anstot] = {st1[j],arr[i]};
			if( g[st1[j]] != arr[i] ) st2[++st2[0]] = st1[j];
		}
		for(auto j: cl[arr[i]]) st2[++st2[0]] = 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( find(i) != find(g[i]) ) add(find(i),g[i]);
		unite(i,g[i],1);
	}
	for(int i=1;i<=n;i++)	
		if( f[i] != g[i] && !frt[g[i]] ) { puts("NO"); return; } 
	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;
} 

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3856kb

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

result:

ok good! (YES count = 4, NO count = 1) (5 test cases)

Test #2:

score: -100
Wrong Answer
time: 72ms
memory: 4176kb

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
2
2 1 2
2 5 2
YES
0
YES
6
2 2 3
2 3 4
2 2 4
2 5 4
2 4 1
2 5 1
YES
2
2 3 2
2 5 2
YES
0
YES
2
2 1 5
2 2 3
YES
4
2 3 1
2 2 5
2 5 4
2 2 4
YES
1
2 5 2
YES
1
2 2 3
YES
3
2 1 2
2 3 4
2 5 4
YES
1
2 1 5
YES
5
2 1 4
2 3 4
2 4 5
2 1 5
2 3 5
YES
4
2 3 4
2 4 5
2 3 5
2 5 1
YES
5
2 4 3
2 2 3
2 3 1
2 2 1
2 5 1
...

result:

wrong answer f[3] = 5, but expected 1 (test case 247)