Submission #1222693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222693		thangdz2k7	Teleporters (IOI08_teleporters)	C++20	100 / 100	358 ms	47744 KiB

teleporters

#include <bits/stdc++.h>

using namespace std;

const int MAX = 2e6 + 1;

void process(){
	int n, m; cin >> n >> m;
	vector <int> w(n), e(n), ord;

	for (int i = 0; i < n; ++ i){
		cin >> w[i] >> e[i];
		ord.push_back(w[i]);
		ord.push_back(e[i]);
	}
	sort(ord.begin(), ord.end());

	vector <int> l(MAX, 0);
	for (int i = 1; i < n * 2; ++ i) 
		l[ord[i]] = ord[i - 1];

	vector <int> root(MAX), siz(MAX, 1);
	iota(root.begin(), root.end(), 0);

	function <int(int)> Find = [&](int u) {
		if (u == root[u]) return u;
		return root[u] = Find(root[u]);
	};

	auto joint = [&](int u, int v) -> void {
		u = Find(u), v = Find(v);
		if (u == v) return;
		if (u < v) swap(u, v);
		root[u] = v;
		siz[v] += siz[u];
	};

	for (int i = 0; i < n; ++ i){
		joint(l[w[i]], e[i]);
		joint(l[e[i]], w[i]);
	}

	vector <int> tmp;
	for (int x : ord) if (x == Find(x)) tmp.push_back(x);

	sort(tmp.begin(), tmp.end(), [&](int u, int v){
		return siz[u] < siz[v];
	});

	int ans = siz[0];
	int flag = 1;

	while (m --){
		if (tmp.size()){
			ans += siz[tmp.back()] + 2;
			tmp.pop_back();
			continue;
		}
		ans += flag;
		flag ^= 2;
	}

	cout << ans - 1;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	process();
	return 0;

}

/*
3
1
1 3
4 6
2 5
*/

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5