oj.uz

Submission #54026

# Submission time Handle Problem Language Result Execution time Memory
54026 2018-07-02T08:33:49 Z 김세빈(#1455) Teleporters (IOI08_teleporters) C++11
15 / 100
 709 ms 34128 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;

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

int main()
{
//	freopen("input.txt", "r", stdin);
	
	int i, j, 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(pii(S[i], i));
		X.push_back(pii(E[i], 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--){
			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:12: warning: unused variable 's' [-Wunused-variable]
  int i, j, s, e, p, cnt;
            ^
teleporters.cpp:17:15: warning: unused variable 'e' [-Wunused-variable]
  int i, j, s, e, p, cnt;
               ^
teleporters.cpp:20: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:23: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 376 KB Output is correct

Subtask #3
5.0 / 5.0

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

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 520 KB Output isn't correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 520 KB Output isn't correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 524 KB Output isn't correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 524 KB Output isn't correct

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 524 KB Output isn't correct

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 524 KB Output isn't correct

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 524 KB Output isn't correct

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 524 KB Output isn't correct

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1240 KB Output isn't correct

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 1360 KB Output isn't correct

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 5320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 131 ms 8668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 388 ms 23060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 609 ms 30568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 709 ms 34128 KB Output isn't correct
2 Halted 0 ms 0 KB -