Znzryb's Blog
0%

ABC-395-D - Pigeon Swap

Posted on Edited on

思路讲解

洛谷很明确的告诉我这道题目就是并查集。但是我不太会就是说这个并查集怎么把单个元素剥离出来的？

哈哈，事实证明他只是借用了一下并查集的思想，并不是真的并查集（不需要find函数和merge函数）

nestTofa的意思就是指nest号码对应到的fa的号码，faTonest的意思就是fa的号码对应到的nest的号码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
if(op==1){
	ll a,b;
	cin>>a>>b;
	fa[a]=nestTofa[b];
}else if(op==2){
	ll a,b;
	cin>>a>>b;
	swap(faTonest[nestTofa[a]],faTonest[nestTofa[b]]);
	swap(nestTofa[a],nestTofa[b]);
}else{
	ll a;
	cin>>a;
	cout<<faTonest[fa[a]]<<"\n";
}

AC代码

https://atcoder.jp/contests/abc395/submissions/64014199

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// Problem: D - Pigeon Swap
// Contest: AtCoder - AtCoder Beginner Contest 395
// URL: https://atcoder.jp/contests/abc395/tasks/abc395_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll N,Q,T,A[MAXN];
ll fa[MAXN];
ll faTonest[MAXN];
ll nestTofa[MAXN];

inline void solve(){
	cin>>N>>Q;
	FOR(i,1,N){
		fa[i]=i;
		faTonest[i]=i;
		nestTofa[i]=i;
	}
	FOR(i,1,Q){
		ll op;
		cin>>op;
		if(op==1){
			ll a,b;
			cin>>a>>b;
			fa[a]=nestTofa[b];
		}else if(op==2){
			ll a,b;
			cin>>a>>b;
			swap(faTonest[nestTofa[a]],faTonest[nestTofa[b]]);
			swap(nestTofa[a],nestTofa[b]);
		}else{
			ll a;
			cin>>a;
			cout<<faTonest[fa[a]]<<"\n";
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	solve();
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc395/submissions/64014199
*/

心路历程（WA，TLE，MLE……）