oj.uz

Submission #54168

# Submission time Handle Problem Language Result Execution time Memory
54168 2018-07-02T14:57:12 Z 0^0(#1448) Teleporters (IOI08_teleporters) C++11
65 / 100
 1000 ms 39996 KB 
#include <bits/stdc++.h>
using namespace std;
int n, m;
pair<int, int> arr[1000005];
vector<pair<int, int> > vec;
int par[2000005];
int sz[2000005];
int find(int x) {
	int temp = x;
	while (par[x] != x) x = par[x];
	while (par[temp] != temp) {
		int ttemp = temp;
		temp = par[temp];
		par[ttemp] = x;
	}
	return x;
}
void merge(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y)return;
	par[x] = y;
	sz[y] += sz[x];
}
int main() {
	scanf("%d%d", &n, &m);
	vec.push_back({ 0,0 });
	vec.push_back({ 2000001,1 });
	par[0] = 0;
	par[1] = 1;
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &arr[i].first, &arr[i].second);
		vec.push_back({ arr[i].first, i * 2 });
		vec.push_back({ arr[i].second,i * 2 + 1 });
		sz[i * 2] = sz[i * 2 + 1] = 1;
		par[i * 2] = i * 2;
		par[i * 2 + 1] = i * 2 + 1;
	}
	sort(vec.begin(), vec.end());
	merge(0, vec[1].second);
	for (int i = 1; i <= n; i++) {
		int le = arr[i].first;
		int ri = arr[i].second;
		merge(i * 2, lower_bound(vec.begin(), vec.end(), make_pair(ri + 1, 0))->second);
		merge(i * 2 + 1, lower_bound(vec.begin(), vec.end(), make_pair(le + 1, 0))->second);
	}
	priority_queue<int> pq;
	for (int i = 0; i < (n + 1) * 2; i++) {
		if (i == find(i) && find(i) != find(0))pq.push(sz[find(i)]);
	}
	int ans = sz[find(0)] + m * 2;
	while (!pq.empty() && m--) {
		ans += pq.top();
		pq.pop();
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message

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

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

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

Subtask #9
5.0 / 5.0

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

Subtask #10
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 748 KB Output is correct
2 Correct 14 ms 1132 KB Output is correct

Subtask #13
0 / 5.0

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

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1256 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1640 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 5972 KB Output is correct
2 Correct 367 ms 15028 KB Output is correct

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 15028 KB Output is correct
2 Incorrect 682 ms 19268 KB Output isn't correct

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1018 ms 29504 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 1084 ms 35192 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 1086 ms 39996 KB Time limit exceeded
2 Halted 0 ms 0 KB -