oj.uz

Submission #54170

# Submission time Handle Problem Language Result Execution time Memory
54170 2018-07-02T15:16:45 Z 0^0(#1448) Teleporters (IOI08_teleporters) C++11
100 / 100
 880 ms 55732 KB 
#include <bits/stdc++.h>
using namespace std;
int n, m;
pair<int, int> arr[1000005];
vector<pair<int, int> > vec;
pair<int, int> nidx[1000005];
int par[2000005];
int sz[2000005];
int find(int x) {
	int ret = x;
	while (par[x] != x)x = par[x];
	while (par[ret] != ret) {
		int temp = ret;
		ret = par[ret];
		par[temp] = x;
	}
	return ret;
}
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());
	for (int i = 1; i + 1 < vec.size(); i++) {
		int idx = vec[i].second;
		if (idx & 1) nidx[idx / 2].second = vec[i + 1].second;
		else nidx[idx / 2].first = vec[i + 1].second;
	}
	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, nidx[i].second);
		merge(i * 2 + 1, nidx[i].first);
	}
	vector<int> t;
	int p = find(0);
	for (int i = 0; i < (n + 1) * 2; i++) {
		int f = find(i);
		if (i == f && f != p)t.push_back(sz[f]);
	}
	sort(t.begin(), t.end());
	int ans = sz[p];
	for (int i = 0; i < t.size() && m; i++, m--)
		ans += t[t.size() - 1 - i] + 2;
	ans += m / 2 * 4;
	ans += m & 1;
	printf("%d\n", ans);
	return 0;
}

Compilation message

teleporters.cpp: In function 'int main()':
teleporters.cpp:41:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i + 1 < vec.size(); i++) {
                  ~~~~~~^~~~~~~~~~~~
teleporters.cpp:48:7: warning: unused variable 'le' [-Wunused-variable]
   int le = arr[i].first;
       ^~
teleporters.cpp:49:7: warning: unused variable 'ri' [-Wunused-variable]
   int ri = arr[i].second;
       ^~
teleporters.cpp:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < t.size() && m; i++, m--)
                  ~~^~~~~~~~~~
teleporters.cpp:27: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:33: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 376 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 436 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
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 540 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 620 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 4 ms 748 KB Output is correct
2 Correct 8 ms 1132 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1132 KB Output is correct
2 Correct 9 ms 1236 KB Output is correct
3 Correct 23 ms 2148 KB Output is correct

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 6940 KB Output is correct
2 Correct 209 ms 15720 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 15720 KB Output is correct
2 Correct 355 ms 22732 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 33588 KB Output is correct
2 Correct 760 ms 39880 KB Output is correct
3 Correct 677 ms 46544 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 675 ms 46544 KB Output is correct
2 Correct 880 ms 49404 KB Output is correct
3 Correct 733 ms 49404 KB Output is correct
4 Correct 751 ms 49404 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 833 ms 54232 KB Output is correct
2 Correct 804 ms 54484 KB Output is correct
3 Correct 446 ms 55680 KB Output is correct
4 Correct 733 ms 55732 KB Output is correct