Submission #229478

#	Time	Username	Problem	Language	Result	Execution time	Memory
229478		apostoldaniel854	Teleporters (IOI08_teleporters)	C++14	5 / 100	1096 ms	29048 KiB

teleporters

#include <bits/stdc++.h>

using namespace std;

const int N = 2e6;

int nxt[2000005];
bool used[1 + N + 1];
typedef long long ll;

int main(){
	for (int i = 1; i <= N; i++)
		nxt[i] = i;
	used[N + 1] = true;
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		nxt[x] = y + 1;
		nxt[y] = x + 1;
	}
	ll ans = -1;
	priority_queue <int> pq;
	for (int i = 1; i <= N; i++) {
		if (used[i] == false) {
            int cur = i, cnt = 0;
			while (used[cur] == false) {
				used[cur] = true;
				if (nxt[cur] != cur + 1)
                    cnt++;
				cur = nxt[cur];
			}
			if (ans == -1)
                ans = cnt;
			else
                pq.push (cnt);
		}
	}
	while (pq.size () && m){
		ans += pq.top () + 2;
		pq.pop ();
		m--;
	}
	ans += (m + 1) / 2;
	ans += (m / 2) * 3;
	cout << ans << "\n";
	return 0;
}

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