QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#374853#6502. Disjoint Set Union514imbaWA 107ms4344kbC++113.0kb2024-04-02 18:52:482024-04-02 18:52:50

Judging History

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

  • [2024-04-02 18:52:50]
  • 评测
  • 测评结果：WA
  • 用时：107ms
  • 内存：4344kb
查看
  • [2024-04-02 18:52:48]
  • 提交

answer

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=b;i>=a;i--)
#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 rd( 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 retNO { puts("NO"); return; }

#define MAXN 1000
int n;
int f[MAXN+5], g[MAXN+5], frt[MAXN+5], flf[MAXN+5], topovis[MAXN+5];
int fa[2][MAXN+5], in[MAXN+5];
vector<int> cl[MAXN+5], to[MAXN+5]; 
struct ansNode {
	int x, y;
}ans[MAXN*MAXN*2+5];int anstot;
void add( int x , int y ) {
	++in[y]; to[x].pb(y);
}
int find( int *fa, int x ) {
	if( fa[x] == x ) return x;
	return fa[x] = find(fa, fa[x]);
}
void unite( int *fa, int x , int y ) {
	x = find(fa,x), y = find(fa,y);
	fa[x] = y;
}
queue<int> q; int st[2][MAXN+5];
int arr[MAXN+5];
#define st1 st[x]
#define st2 st[x^1]
bool topo( int rt ) {
	while( !q.empty() ) q.pop(); arr[0] = 0;
	FOR(i,1,n) if( frt[i] && find(fa[1],i) == rt && !in[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(i,1,n) if( frt[i] && find(fa[1],i) == rt && in[i] ) return false;
	int x = 0; st1[0] = st2[0] = 0;
	for(auto i: cl[arr[1]]) st1[++st1[0]] = i;
	FOR(i,2,arr[0]) {
		if( anstot >= 10000 ) return false;
		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; 
}
void solve(){
	rd(n); FOR(i,1,n) topovis[i] = false, fa[0][i] = fa[1][i] = i, frt[i] = false, flf[i] = true, cl[i].clear(), to[i].clear(), in[i] = 0; anstot = 0;
	FOR(i,1,n) rd(f[i]); FOR(i,1,n) rd(g[i]);
	FOR(i,1,n) { if( find(fa[0],i) == find(fa[0],f[i]) && i != f[i] ) retNO unite(fa[0],i,f[i]);} FOR(i,1,n) unite(fa[1],i,g[i]);
	FOR(i,1,n) frt[find(fa[0],i)] = true, flf[f[i]] = false;
	FOR(i,1,n) if( find(fa[1],i) != find(fa[1],f[i]) ) retNO
	FOR(i,1,n) {
		if( f[i] != g[i] ) {
			if( !frt[g[i]] ) retNO
			if( find(fa[0],i) != find(fa[0],g[i]) )add(find(fa[0],i), g[i]);
		}
	}
	FOR(i,1,n) if( flf[i] && !frt[i] ) {
		int p=i;
		for(bool chg=false;!frt[f[p]];p=f[p]) {
			if( chg && f[p] == g[p] ) retNO
			if( f[p] != g[p] ) { chg = true, ans[++anstot] = {p,find(fa[0],p)}; if( g[p] != find(fa[0],p) ) cl[find(fa[0],p)].pb(p);}
		}
		if( f[p] != g[p] ) cl[find(fa[0],p)].pb(p);
	}
	FOR(i,1,n) if( !topovis[find(fa[1],i)] ) {
		if( !topo(find(fa[1],i)) ) retNO
		topovis[find(fa[1],i)] = true;
	}
	puts("YES"); printf("%d\n", anstot);
	FOR(i,1,anstot) printf("2 %d %d\n",ans[i].x,ans[i].y);
	return;
}

int main() {
//	freopen("test.in","r",stdin);
	int t; rd(t);
	while( t-- ) solve();
	return 0; 
}
Source code, Language: C++11

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0
Accepted
time: 78ms
memory: 3908kb

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:

ok good! (YES count = 100000, NO count = 0) (100000 test cases)

Test #3:

score: 0
Accepted
time: 107ms
memory: 3868kb

input:

50000
10
1 2 3 4 5 6 7 8 6 10
1 10 3 4 5 6 7 8 6 10
10
6 2 3 4 5 6 2 5 5 10
6 6 6 6 6 6 6 6 6 10
10
1 2 3 4 7 7 7 10 9 10
9 7 3 9 9 9 9 9 9 7
10
1 2 3 7 4 2 3 8 3 10
2 2 2 2 2 2 2 2 2 2
10
1 2 3 5 5 8 2 8 9 10
2 2 3 5 10 8 2 10 9 10
10
1 8 3 3 5 6 10 8 9 10
5 5 5 5 5 5 5 5 5 5
10
8 2 7 4 5 6 8 8 9 1...

output:

YES
1
2 2 10
YES
16
2 2 3
2 7 3
2 3 4
2 2 4
2 7 4
2 4 5
2 3 5
2 2 5
2 7 5
2 5 6
2 4 6
2 3 6
2 2 6
2 7 6
2 8 6
2 9 6
YES
17
2 1 2
2 2 4
2 1 4
2 4 10
2 2 10
2 1 10
2 10 7
2 4 7
2 2 7
2 1 7
2 8 7
2 7 9
2 4 9
2 1 9
2 8 9
2 5 9
2 6 9
YES
24
2 5 3
2 4 3
2 1 3
2 3 8
2 1 8
2 5 8
2 4 8
2 7 8
2 9 8
2 8 10
2 3...

result:

ok good! (YES count = 50000, NO count = 0) (50000 test cases)

Test #4:

score: 0
Accepted
time: 67ms
memory: 3808kb

input:

12500
20
9 2 3 4 5 6 7 8 9 10 11 9 13 14 19 19 17 18 19 20
8 2 3 6 4 6 7 18 18 10 3 8 6 4 19 4 4 4 4 20
20
6 2 3 4 6 15 7 8 9 10 11 12 13 14 15 20 17 18 19 20
12 12 2 8 12 12 7 12 9 12 11 12 13 14 12 8 8 9 8 8
20
5 2 3 4 5 20 7 8 9 10 11 10 13 14 20 16 10 18 19 9
19 19 4 4 19 3 14 8 3 4 3 4 3 14 3 1...

output:

YES
50
2 5 9
2 9 13
2 5 13
2 1 13
2 12 13
2 13 14
2 9 14
2 5 14
2 1 14
2 12 14
2 14 17
2 13 17
2 9 17
2 5 17
2 1 17
2 12 17
2 17 19
2 14 19
2 13 19
2 9 19
2 5 19
2 1 19
2 12 19
2 19 8
2 17 8
2 14 8
2 13 8
2 9 8
2 5 8
2 1 8
2 12 8
2 16 8
2 8 18
2 19 18
2 17 18
2 14 18
2 13 18
2 9 18
2 5 18
2 16 18
2 ...

result:

ok good! (YES count = 12500, NO count = 0) (12500 test cases)

Test #5:

score: 0
Accepted
time: 75ms
memory: 3768kb

input:

12500
20
1 2 3 4 5 6 7 7 5 10 11 12 13 14 5 16 17 5 19 20
10 3 12 3 3 3 4 12 3 10 3 12 3 3 13 3 11 11 13 2
20
1 2 3 10 5 6 7 13 12 10 11 13 13 13 13 16 17 13 19 20
13 13 3 10 13 13 1 13 13 13 13 13 13 13 13 13 13 13 13 13
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 9 3 4 17 6 7 19 9 10 1...

output:

YES
112
2 1 10
2 5 6
2 9 6
2 15 6
2 18 6
2 6 7
2 5 7
2 9 7
2 15 7
2 18 7
2 7 14
2 6 14
2 5 14
2 9 14
2 15 14
2 18 14
2 8 14
2 14 16
2 7 16
2 6 16
2 5 16
2 9 16
2 15 16
2 18 16
2 8 16
2 16 17
2 14 17
2 7 17
2 6 17
2 5 17
2 9 17
2 15 17
2 18 17
2 8 17
2 17 19
2 16 19
2 14 19
2 7 19
2 6 19
2 5 19
2 9 1...

result:

ok good! (YES count = 12500, NO count = 0) (12500 test cases)

Test #6:

score: 0
Accepted
time: 81ms
memory: 3972kb

input:

500
100
5 43 3 13 100 6 56 8 9 62 11 82 13 14 15 48 17 76 19 64 35 62 50 77 38 94 35 62 35 30 31 32 48 34 35 36 43 64 39 40 35 42 62 44 45 62 47 62 49 50 62 47 62 62 39 48 20 58 59 60 43 66 19 62 3 66 67 85 69 70 83 28 73 83 100 76 77 80 85 80 81 82 100 84 85 40 20 88 62 90 40 92 93 94 58 96 30 98 6...

output:

YES
2648
2 1 94
2 5 94
2 2 66
2 43 66
2 7 66
2 56 66
2 48 66
2 10 66
2 16 66
2 48 66
2 22 66
2 25 66
2 38 66
2 64 66
2 33 66
2 48 66
2 37 66
2 43 66
2 46 66
2 51 66
2 53 66
2 54 66
2 57 66
2 20 66
2 64 66
2 61 66
2 43 66
2 71 94
2 83 94
2 72 66
2 28 66
2 74 94
2 83 94
2 75 94
2 87 66
2 20 66
2 64 66...

result:

ok good! (YES count = 500, NO count = 0) (500 test cases)

Test #7:

score: -100
Wrong Answer
time: 6ms
memory: 4344kb

input:

55
300
172 231 135 149 135 297 7 297 236 52 73 114 52 135 15 73 297 97 218 236 52 236 218 73 244 236 73 52 162 218 103 30 214 34 59 36 73 89 44 131 73 73 73 73 73 41 47 32 236 52 248 73 73 54 209 75 57 73 205 151 73 62 73 73 143 141 238 205 106 73 71 128 73 124 75 76 89 231 205 73 149 135 249 135 13...

output:

NO
YES
3006
2 1 181
2 2 181
2 3 181
2 4 181
2 5 181
2 55 181
2 7 181
2 17 181
2 9 181
2 10 181
2 11 181
2 76 181
2 12 181
2 13 181
2 14 181
2 16 181
2 53 181
2 18 181
2 19 181
2 20 181
2 21 181
2 89 181
2 22 181
2 126 181
2 23 181
2 24 181
2 25 181
2 26 181
2 196 181
2 27 181
2 123 181
2 28 181
2 29...

result:

wrong answer you didn't find a solution but jury did (test case 1)
English 繁體中文 简体中文

Server Time: 2024-12-04 22:55:28 | OpenSource Project