oj.uz

Submission #396607

# Submission time Handle Problem Language Result Execution time Memory
396607 2021-04-30T12:26:53 Z Berted Teleporters (IOI08_teleporters) C++14
100 / 100
 732 ms 38864 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 6 ms 724 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 7 ms 716 KB Output is correct
3 Correct 14 ms 1352 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 792 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 848 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 3812 KB Output is correct
2 Correct 197 ms 8200 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 6088 KB Output is correct
2 Correct 337 ms 11784 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 17344 KB Output is correct
2 Correct 518 ms 20392 KB Output is correct
3 Correct 448 ms 24128 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 23512 KB Output is correct
2 Correct 722 ms 38864 KB Output is correct
3 Correct 531 ms 38084 KB Output is correct
4 Correct 557 ms 38456 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 732 ms 28368 KB Output is correct
2 Correct 708 ms 28376 KB Output is correct
3 Correct 469 ms 28228 KB Output is correct
4 Correct 547 ms 28476 KB Output is correct