Submission #98867

#	Time	Username	Problem	Language	Result	Execution time	Memory
98867		shoemakerjo	Teleporters (IOI08_teleporters)	C++14	100 / 100	794 ms	45160 KiB

teleporters

#include <bits/stdc++.h>

using namespace std;

int N, M;
const int maxn = 2000010;

int aft[maxn];
int bef[maxn];

bool isin[maxn];
bool vis[maxn];

int a[maxn], b[maxn];
int previn[maxn];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	fill(aft, aft+maxn, -1);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> a[i] >> b[i];
		isin[a[i]] = true;
		isin[b[i]] = true;
	}

	int cp = 0;
	for (int i = 1; i < maxn; i++) {
		if (isin[i]) {
			previn[i] = cp;
			cp = i;
		}
	}
	for (int i = 0; i < N; i++) {
		aft[previn[a[i]]] = b[i];
		bef[b[i]] = previn[a[i]];

		// cout << "thing: " << previn[a[i]] << " - " << b[i] << 
		// 	" :: " << a[i] <<  endl;

		aft[previn[b[i]]] = a[i];
		bef[a[i]] = previn[b[i]];
	}
	isin[0] = true;

	vector<int> cyclen;
	int clen = 0;
	for (int i = 0; i < maxn; i++) {
		if (!isin[i] || vis[i]) continue;

		int cv = 0;
		int u = i;
		bool ip = false;
		// cout << "  path: ";
		while (!vis[u]) {

			// cout << u << " ";

			cv++;
			vis[u] = true;
			u = aft[u];
			if (u == -1) {
				ip = true;
				clen = cv-1;
				break;
			}
		}
		// cout << u << endl;

		if (!ip) cyclen.push_back(cv);
	}
	sort(cyclen.begin(), cyclen.end());
	reverse(cyclen.begin(), cyclen.end());

	// cout << "this: " << clen << endl;

	for (int i = 0; i < cyclen.size(); i++) {
		if (M == 0) break;
		M--;
		clen += cyclen[i] + 2;
	}

	if (M) {
		int d2 = M/2;
		if (M %2 == 1) clen++;
		clen += d2 * 4;
	}
	cout << clen << endl;

}

Compilation message (stderr)

teleporters.cpp: In function 'int main()':
teleporters.cpp:79:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < cyclen.size(); i++) {
                  ~~^~~~~~~~~~~~~~~

• 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