oj.uz

답안 #54033

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
54033 2018-07-02T08:41:35 Z 김세빈(#1455) Teleporters (IOI08_teleporters) C++11
100 / 100
 762 ms 30296 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;

vector <pii> X;
int P[2020202], R[1010101], K[2020202];
bool chk[2020202];
int n, m, ans;

int main()
{
	int i, j, s, e, p, cnt;
	bool prev;
	
	scanf("%d%d", &n, &m);
	
	for(i=0;i<n;i++){
		scanf("%d%d", &s, &e);
		X.push_back(pii(s, i));
		X.push_back(pii(e, i));
	}
	
	sort(X.begin(), X.end());
	
	for(i=0;i<n+n;i++){
		if(R[X[i].second]){
			P[R[X[i].second]] = i+1;
			P[i+1] = R[X[i].second];
		}
		else R[X[i].second] = i+1;
	}
	
	prev = true;
	for(p=0;p!=2*n+1;){
		if(prev){
			chk[p] = 1;
			p = p+1;
			prev = false;
		}
		else{
			p = P[p];
			ans ++;
			prev = true;
		}
	}
	
	for(i=1;i<=2*n;i++){
		if(!chk[i]){
			prev = true;
			for(cnt=0,p=i;;){
				if(prev){
					chk[p] = 1;
					p = p+1;
					prev = false;
				}
				else{
					p = P[p];
					cnt ++;
					prev = true;
				}
				if(p == i) break;
			}
			K[cnt] ++;
		}
	}
	
	for(i=n+n;i>=1;i--){
		for(j=0;j<K[i] && m;m--,j++){
			ans += i + 2;
		}
		if(!m) break;
	}
	
	ans += m*2 - m%2;
	
	printf("%d\n", ans);
	
	return 0;
}

Compilation message

teleporters.cpp: In function 'int main()':
teleporters.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
teleporters.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &s, &e);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

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

Subtask #9
5.0 / 5.0

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

Subtask #10
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 720 KB Output is correct
2 Correct 6 ms 976 KB Output is correct

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 976 KB Output is correct
2 Correct 11 ms 996 KB Output is correct
3 Correct 17 ms 1628 KB Output is correct

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 4372 KB Output is correct
2 Correct 232 ms 9544 KB Output is correct

Subtask #17
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 9544 KB Output is correct
2 Correct 294 ms 13828 KB Output is correct

Subtask #18
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 442 ms 18992 KB Output is correct
2 Correct 538 ms 22756 KB Output is correct
3 Correct 536 ms 24968 KB Output is correct

Subtask #19
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 762 ms 26664 KB Output is correct
2 Correct 726 ms 28768 KB Output is correct
3 Correct 621 ms 29964 KB Output is correct
4 Correct 656 ms 30288 KB Output is correct

Subtask #20
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 606 ms 30288 KB Output is correct
2 Correct 654 ms 30296 KB Output is correct
3 Correct 444 ms 30296 KB Output is correct
4 Correct 592 ms 30296 KB Output is correct