oj.uz

Submission #54020

# Submission time Handle Problem Language Result Execution time Memory
54020 2018-07-02T08:29:25 Z 김세빈(#1455) Teleporters (IOI08_teleporters) C++11
85 / 100
 1000 ms 20536 KB 
#include <bits/stdc++.h>

using namespace std;

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

int main()
{
	int i, s, e, p, cnt;
	bool prev;
	
	scanf("%d%d", &n, &m);
	
	for(i=0;i<n;i++){
		scanf("%d%d", S+i, E+i);
		X.push_back(S[i]);
		X.push_back(E[i]);
	}
	
	sort(X.begin(), X.end());
	
	for(i=0;i<n;i++){
		s = (lower_bound(X.begin(), X.end(), S[i]) - X.begin()) + 1;
		e = (lower_bound(X.begin(), X.end(), E[i]) - X.begin()) + 1;
		P[s] = e; P[e] = s;
	}
	
	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.push_back(cnt);
		}
	}
	
	sort(K.begin(), K.end());
	
	for(;!K.empty() && m;m--){
		ans += K.back() + 2;
		K.pop_back();
	}
	
	ans += m*2 - m%2;
	
	printf("%d\n",ans);
	
	return 0;
}

Compilation message

teleporters.cpp: In function 'int main()':
teleporters.cpp:16: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:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", S+i, E+i);
   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

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

Subtask #9
5.0 / 5.0

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

Subtask #10
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 8 ms 1004 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1004 KB Output is correct
2 Correct 10 ms 1004 KB Output is correct
3 Correct 21 ms 1512 KB Output is correct

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 4312 KB Output is correct
2 Correct 287 ms 9336 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 9336 KB Output is correct
2 Correct 449 ms 13176 KB Output is correct

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 14404 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 18352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 20536 KB Time limit exceeded
2 Halted 0 ms 0 KB -