제출 #790356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
790356		pavement	Teleporters (IOI08_teleporters)	C++17	70 / 100	1074 ms	42512 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];
ii frnt[1000005], back[1000005];
vector<int> vec;

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;
	}
};

void counting_sort(vector<int> vec) {
	vector<int> freq(N + 1, 0);
	int idx = 0;
	for (int i : vec) freq[i]++;
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j < freq[i]; j++) vec[idx++] = i;
	}
}

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[i - 1] = mp(W[i], i);
		back[i - 1] = mp(E[i], N + i);
	}
	sort(frnt, frnt + N);
	sort(back, back + N);
	for (int i = 1; i <= N; i++) {
		// i_f
		auto it = upper_bound(frnt, frnt + N, mp(E[i], (int)1e9));
		auto it2 = upper_bound(back, back + N, mp(E[i], (int)1e9));
		if (it != frnt + N && it2 != back + N) {
			to[i] = (it->first < it2->first ? it->second : it2->second);
		} else if (it == frnt + N && it2 == back + N) {
			
		} else {
			to[i] = it == frnt + N ? it2->second : it->second;
		}
		// i_b
		it = upper_bound(frnt, frnt + N, mp(W[i], (int)1e9));
		it2 = upper_bound(back, back + N, mp(W[i], (int)1e9));
		if (it != frnt + N && it2 != back + N) {
			to[i + N] = (it->first < it2->first ? it->second : it2->second);
		} else if (it == frnt + N && it2 == back + N) {
			
		} else {
			to[i + N] = it == frnt + N ? it2->second : it->second;
		}
	}
	ufds::init(2 * N);
	for (int i = 1; i <= 2 * N; i++) {
		if (to[i]) ufds::unite(i, to[i]);
	}
	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)];
	}
	counting_sort(vec);
	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: 0 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 5 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5