oj.uz

Submission #98866

# Submission time Handle Problem Language Result Execution time Memory
98866 2019-02-27T02:44:29 Z shoemakerjo Teleporters (IOI08_teleporters) C++14
60 / 100
 810 ms 45560 KB 
#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]];
	}

	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;
				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

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

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 8256 KB Output isn't correct

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 8192 KB Output isn't correct

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 8164 KB Output isn't correct

Subtask #10
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8576 KB Output is correct
2 Correct 20 ms 8952 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8524 KB Output is correct
2 Correct 20 ms 9572 KB Output is correct
3 Correct 22 ms 9336 KB Output is correct

Subtask #14
5.0 / 5.0

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

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 8960 KB Output isn't correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 16248 KB Output is correct
2 Correct 272 ms 31680 KB Output is correct

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 156 ms 25464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 494 ms 40244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 659 ms 42300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 810 ms 45560 KB Output is correct
2 Incorrect 767 ms 45392 KB Output isn't correct
3 Halted 0 ms 0 KB -