QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#374868#6502. Disjoint Set Union514imbaWA 111ms4176kbC++113.1kb2024-04-02 18:58:592024-04-02 18:59:00

Judging History

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

  • [2024-04-02 18:59:00]
  • 评测
  • 测评结果：WA
  • 用时：111ms
  • 内存：4176kb
查看
  • [2024-04-02 18:58:59]
  • 提交

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( n == 1000 ) printf("%d ",anstot);
		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;
		if( st2[0] > n ) return false;
		x^=1;
	}
	return true; 
}
int t;
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;
	if( n == 1000 ) t = 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);
	rd(t);
	while( t-- ) solve();
	return 0; 
}
源文件, 语言: C++11

详细

Test #1:

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

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: 3764kb

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: -100
Wrong Answer
time: 111ms
memory: 3844kb

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:

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

服务器时间: 2024-12-05 07:40:41 | 开源项目