QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#369000#6502. Disjoint Set Union514imbaWA 1ms5848kbC++113.3kb2024-03-27 19:12:372024-03-27 19:12:37

Judging History

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

  • [2024-03-27 19:12:37]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5848kb
  • [2024-03-27 19:12:37]
  • 提交

answer

#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define Mp make_pair
#define retNO {puts("NO"); return;}
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 MAXI 3
#define MAXN 1000
int n;
int f[MAXN+5], g[MAXN+5], frt[MAXN+5], frts[MAXN+5];
int fa[MAXI][MAXN+5];
void init( int idx ) {
	for(int i=1;i<=n;i++) fa[idx][i] = i;
}
int find( int idx, int x ) {
	if( fa[idx][x] == x ) return x;
	return fa[idx][x] = find(idx, fa[idx][x]);
}
void merge( int idx , int x , int y ) {
	x = find(idx, x);
	y = find(idx, y);
	if( x != y ) fa[idx][x] = y;
}
bool vis[MAXN+5];
bool chk( int idx , int x , int dep = 0 ) {
	vis[x] = true;
	if( dep > n ) return true;
	if( fa[idx][x] == x ) return false;
	return chk(idx,fa[idx][x],dep+1);
}

vector<int> to[MAXN+5]; int in[MAXN+5];
void add( int u , int v ) {
	to[u].pb(v); ++in[v]; 
}

pair<int,int> ans[MAXN*MAXN+5]; int anstot;
vector<int> hang[MAXN+5]; 
queue<int> q;
vector<pair<int,int> > seq[MAXN+5];
stack<pair<int,int> > s;
bool topo() {
	while( !q.empty() ) q.pop();
	for(int i=1;i<=n;i++) if( frt[i] && !in[i] ) q.push(i);
	while( !q.empty() ) {
		int u = q.front(); q.pop();
		for(auto v: to[u]) {
			hang[v].pb(u); 
			if( --in[v] == 0 ) {
				for(auto k: hang[v]) {	
					ans[++anstot] = Mp(k,v);
					if( !frt[k] ) ans[++anstot] = Mp(k,0); frt[k] = false;
					for(auto l: seq[k]) {
						ans[++anstot] = Mp(l.fi,0);
						if( l.se != v ) seq[v].pb(l);
					}
					seq[k].clear();
				}
				q.push(v);
			}
		}
	}
	for(int i=1;i<=n;i++) if( in[i] ) return false;
	return true;
}

vector<int> to0[MAXN+5];
void add0( int u , int v ) {
	if( u == v ) return;
	to0[u].pb(v);
}
bool chkf = true;
bool dfs0( int u, int fa, int dep = 0 ) {
	bool ret = false;
	for(auto v: to0[u]){
		bool tmp = dfs0(v, u, true);
		if( tmp && g[v] == u && dep ) chkf = false;
		ret |= tmp;
	}
	return ret | g[u] != fa;
}

void solve() {
	read(n);
	for(int i=1;i<=n;i++) read(f[i]), add0(f[i],i); memcpy(fa[0], f, sizeof(f));
	memset(vis,false,sizeof(vis)); for(int i=1;i<=n;i++) if( !vis[i] && chk(0,i) ) retNO
	for(int i=1;i<=n;i++) read(g[i]); memcpy(fa[1], g, sizeof(g));
	memset(vis,false,sizeof(vis)); for(int i=1;i<=n;i++) if( !vis[i] && chk(1,i) ) retNO
	for(int i=1;i<=n;i++) if( find(1,i) != find(1,f[i]) ) retNO
	
	for(int i=1;i<=n;i++) if( !frt[find(0,i)] )
		frts[++frts[0]] = find(0,i), frt[find(0,i)] = true;
	
	chkf = true; for(int i=1;i<=n;i++) if( frt[i] ) dfs0(i,0); if( !chkf ) retNO
	for(int i=1;i<=n;i++) if( g[i] != f[i] ) {
		if( !frt[g[i]] ) retNO
		if( find(0,i) != g[i] )
			add(find(0,i), g[i]);
		if( find(0,i) != i ) {
			if( f[i] != find(0,i) ) ans[++anstot] = Mp(i,0);
			if( find(0,i) != g[i] ) seq[find(0,i)].pb(Mp(i, g[i]));
		}
	}
	if( !topo() ) retNO
	puts("YES"); printf("%d\n",anstot);
	for(int i=1;i<=anstot;i++) {
		if( ans[i].se ) printf("2 %d %d\n", ans[i].fi, ans[i].se);
		else printf("1 %d\n", ans[i].fi);
	}
}

int main() {
	int t;
	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: 5848kb

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
NO
NO
NO
NO

result:

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