Submission #396607

#	Time	Username	Problem	Language	Result	Execution time	Memory
396607		Berted	Teleporters (IOI08_teleporters)	C++14	100 / 100	732 ms	38864 KiB

teleporters

#include <iostream>
#include <algorithm>
#include <vector>
#include <bitset>
#define pii pair<int, int>
#define fst first
#define snd second

using namespace std;

const int MX = 2000000;

int N, K, res = 0;
int nex[MX + 5];
pii A[MX + 5];
bitset<MX + 5> vis;
vector<int> cyc;

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> K;
	for (int i = 0; i < N; i++)
	{
		cin >> A[2 * i].fst >> A[2 * i].snd;
		A[2 * i + 1] = {A[2 * i].snd, A[2 * i].fst};
	}
	A[2 * N] = {0, 0}; A[2 * N + 1] = {MX + 1, -1};
	sort(A, A + 2 * N + 2);

	for (int i = 0; i < 2 * N + 2; i++)
	{
		if (A[i].snd != -1) nex[i] = upper_bound(A, A + 2 * N + 2, make_pair(A[i].snd, MX + 1)) - A;
		else nex[i] = -1;
	}

	int u = 0;
	while (u != -1) {res++; vis[u] = 1; u = nex[u];}

	for (int i = 0; i < 2 * N + 2; i++)
	{
		if (!vis[i])
		{
			u = i; int s = 0;
			while (!vis[u]) {vis[u] = 1; u = nex[u]; s++;}
			cyc.push_back(s);
		}
	}

	sort(cyc.begin(), cyc.end(), greater<int>());

	for (int i = 0; i < cyc.size() && K > 0; i++, K--) res += cyc[i] + 2;

	cout << res + 4 * (K / 2) + (K % 2) - 2 << "\n";
	return 0;
}

Compilation message (stderr)

teleporters.cpp: In function 'int main()':
teleporters.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for (int i = 0; i < cyc.size() && K > 0; i++, K--) res += cyc[i] + 2;
      |                  ~~^~~~~~~~~~~~

• 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