Submission #229483

#	Time	Username	Problem	Language	Result	Execution time	Memory
229483		apostoldaniel854	Teleporters (IOI08_teleporters)	C++14	100 / 100	413 ms	29036 KiB

teleporters

#include <bits/stdc++.h>

using namespace std;

const int N = 2e6;

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

int main(){
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
	for (int i = 1; i <= N; i++)
		nxt[i] = i + 1;
	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;
	}
	int 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: 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