RT

abc 277 C题

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
int n, a[N], b[N], fa[N], backup[N];
int FindSet(int x) {
	if (x == fa[x]) return x;
	return fa[x] = FindSet(fa[x]);
}
map<int, int> mp;
bool f = 0;
int main() {
	cin >> n;
	for (int i = 1;i <= n * 2;i++) fa[i] = i;
	for (int i = 1;i <= n;i++) {
		cin >> a[i] >> b[i];
		if (a[i] > b[i]) swap(a[i], b[i]);
		if (a[i] == 1 || b[i] == 1) f = 1;
		backup[i] = a[i], backup[i + n] = b[i];
	}
	if (!f) {
		cout << 1;
		return 0;
	}
	sort(backup + 1, backup + (n << 1) + 1);
	int cnt = unique(backup + 1, backup + (n << 1) + 1) - backup;
	for (int i = 1;i <= n;i++) {
		int x = lower_bound(backup + 1, backup + cnt + 1, a[i]) - backup, y = lower_bound(backup + 1, backup + cnt + 1, b[i]) - backup;
		mp[x] = a[x], mp[y] = b[i];
		a[i] = x;
		b[i] = y;
		//cout << a[i] <<" " << b[i] << endl;
	}
	for (int i = 1;i <= n;i++) {
		int U = FindSet(a[i]), V = FindSet(b[i]);
		//cout << fa[U] <<" " << fa[V] << endl;
		if (fa[U] < fa[V]) fa[V] = fa[U];
		else fa[U] = fa[V];
	}
	int ans = 1;
	n <<= 1;
	for (int i = 1;i <= n;i++) {
		if (FindSet(i) == 1) ans = max(ans, mp[i]);
	}
	cout << ans;
	return 0;
}

atcoder上的测试点情况：

Case Name Status Exec Time Memory

example0.txt 8 ms 3444 KB AC

example1.txt 2 ms 3396 KB AC

example2.txt 2 ms 3448 KB AC

handmade0.txt 2 ms 3508 KB AC

handmade1.txt 2 ms 3552 KB AC

handmade2.txt 3 ms 3428 KB AC

killer0.txt 359 ms 17364 KB WA

killer1.txt 214 ms 12804 KB AC

killer2.txt 167 ms 10956 KB AC

killer3.txt 264 ms 14036 KB AC

killer4.txt 215 ms 13344 KB WA

killer5.txt 287 ms 15692 KB AC

killer6.txt 162 ms 7912 KB AC

random0.txt 111 ms 7900 KB AC

random1.txt 84 ms 6804 KB AC

random2.txt 252 ms 11588 KB AC

random3.txt 165 ms 9012 KB AC

random4.txt 298 ms 12828 KB AC