oj.uz

답안 #98867

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
98867 2019-02-27T02:48:44 Z shoemakerjo Teleporters (IOI08_teleporters) C++14
100 / 100
 794 ms 45160 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]];
	}
	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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 8192 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 8192 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 8192 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 8232 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 8184 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 8220 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 8192 KB Output is correct

Subtask #8
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 8192 KB Output is correct

Subtask #9
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 8192 KB Output is correct

Subtask #10
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 8192 KB Output is correct

Subtask #11
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 8192 KB Output is correct

Subtask #12
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 8448 KB Output is correct
2 Correct 19 ms 8796 KB Output is correct

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 8448 KB Output is correct
2 Correct 20 ms 9472 KB Output is correct
3 Correct 26 ms 9012 KB Output is correct

Subtask #14
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 8632 KB Output is correct

Subtask #15
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 8716 KB Output is correct

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 14480 KB Output is correct
2 Correct 265 ms 27232 KB Output is correct

Subtask #17
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 179 ms 22616 KB Output is correct
2 Correct 386 ms 37860 KB Output is correct

Subtask #18
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 491 ms 34808 KB Output is correct
2 Correct 550 ms 41232 KB Output is correct
3 Correct 549 ms 40556 KB Output is correct

Subtask #19
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 716 ms 36788 KB Output is correct
2 Correct 712 ms 42896 KB Output is correct
3 Correct 699 ms 40960 KB Output is correct
4 Correct 681 ms 41208 KB Output is correct

Subtask #20
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 794 ms 39836 KB Output is correct
2 Correct 733 ms 40060 KB Output is correct
3 Correct 301 ms 45160 KB Output is correct
4 Correct 679 ms 45104 KB Output is correct