oj.uz

Submission #54032

# Submission time Handle Problem Language Result Execution time Memory
54032 2018-07-02T08:40:33 Z 김세빈(#1455) Teleporters (IOI08_teleporters) C++11
85 / 100
 596 ms 48088 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;

vector <pii> X;
int P[1010101], 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

# 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 376 KB Output is correct

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

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

Subtask #9
5.0 / 5.0

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

Subtask #10
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 748 KB Output is correct
2 Correct 10 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 9 ms 1128 KB Output is correct
3 Correct 15 ms 1636 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1636 KB Output is correct

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 4460 KB Output is correct
2 Correct 173 ms 9668 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 9668 KB Output is correct
2 Correct 259 ms 13920 KB Output is correct

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 529 ms 43308 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 596 ms 48088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -