oj.uz

Submission #54015

# Submission time Handle Problem Language Result Execution time Memory
54015 2018-07-02T08:21:04 Z 김세빈(#1455) Teleporters (IOI08_teleporters) C++11
75 / 100
 1000 ms 40428 KB 
#include <bits/stdc++.h>

using namespace std;

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

int main()
{
	int i, s, e, p, cnt;
	
	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<=4*n;i++) P[i] = i+1;
	
	for(i=0;i<n;i++){
		s = (lower_bound(X.begin(), X.end(), S[i]) - X.begin()) * 2 + 1;
		e = (lower_bound(X.begin(), X.end(), E[i]) - X.begin()) * 2 + 1;
		P[s] = e+1; C[s] = 1;
		P[e] = s+1; C[e] = 1;
	}
	
	for(p=0;p!=4*n+1;p=P[p]){
		chk[p] = 1;
		ans += C[p];
	}
	
	for(i=1;i<=4*n;i++){
		if(!chk[i]){
			for(cnt=0,p=i;;p=P[p]){
				chk[p] = 1;
				cnt += C[p];
				if(P[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:15: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:18: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 2 ms 376 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 568 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 596 KB Output is correct

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 724 KB Output is correct
2 Correct 8 ms 1236 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1236 KB Output is correct
2 Correct 10 ms 1364 KB Output is correct
3 Correct 22 ms 2256 KB Output is correct

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 7436 KB Output is correct
2 Execution timed out 1076 ms 13400 KB Time limit exceeded

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 13400 KB Output is correct
2 Execution timed out 1082 ms 16840 KB Time limit exceeded

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 452 ms 38460 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 514 ms 40428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -