Submission #790347

#	Time	Username	Problem	Language	Result	Execution time	Memory
790347		pavement	Teleporters (IOI08_teleporters)	C++17	90 / 100	1057 ms	62084 KiB

teleporters

#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define eb emplace_back

using ii = pair<int, int>;

int N, M, to_remove, W[1000005], E[1000005], to[2000005];
vector<int> vec;
vector<ii> frnt, back;

namespace ufds {
	int lnk[2000005], sz[2000005];
	
	void init(int n) {
		iota(lnk + 1, lnk + 1 + n, 1);
		fill(sz + 1, sz + 1 + n, 1);
	}
	int find(int x) {
		if (x == lnk[x]) return x;
		return lnk[x] = find(lnk[x]);
	}
	void unite(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b) return;
		if (sz[b] > sz[a]) swap(a, b);
		sz[a] += sz[b];
		lnk[b] = a;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> W[i] >> E[i];
		frnt.eb(W[i], i);
		back.eb(E[i], N + i);
	}
	sort(frnt.begin(), frnt.end());
	sort(back.begin(), back.end());
	for (int i = 1; i <= N; i++) {
		// i_f
		auto it = upper_bound(frnt.begin(), frnt.end(), mp(E[i], (int)1e9));
		auto it2 = upper_bound(back.begin(), back.end(), mp(E[i], (int)1e9));
		if (it != frnt.end() && it2 != back.end()) {
			to[i] = (it->first < it2->first ? it->second : it2->second);
		} else if (it == frnt.end() && it2 == back.end()) {
			
		} else {
			to[i] = it == frnt.end() ? it2->second : it->second;
		}
		// i_b
		it = upper_bound(frnt.begin(), frnt.end(), mp(W[i], (int)1e9));
		it2 = upper_bound(back.begin(), back.end(), mp(W[i], (int)1e9));
		if (it != frnt.end() && it2 != back.end()) {
			to[i + N] = (it->first < it2->first ? it->second : it2->second);
		} else if (it == frnt.end() && it2 == back.end()) {
			
		} else {
			to[i + N] = it == frnt.end() ? it2->second : it->second;
		}
	}
	ufds::init(2 * N);
	for (int i = 1; i <= 2 * N; i++) {
		if (to[i]) ufds::unite(i, to[i]);
	}
	assert(count(to + 1, to + 1 + 2 * N, 0) == 1);
	for (int i = 1; i <= 2 * N; i++) {
		if (i == ufds::find(i)) vec.pb(ufds::sz[i]);
		if (!to[i]) to_remove = ufds::sz[ufds::find(i)];
	}
	sort(vec.begin(), vec.end(), greater<int>());
	vec.erase(find(vec.begin(), vec.end(), to_remove));
	int ans = 2 * M + to_remove;
	for (int i = 0; i < min((int)vec.size(), M); i++) {
		ans += vec[i];
	}
	if (M > (int)vec.size() && (M - (int)vec.size()) % 2 == 1) ans--;
	cout << ans << '\n';
}

• 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: 0 / 5
• Subtask 20: 0 / 5