oj.uz

Submission #54169

# Submission time Handle Problem Language Result Execution time Memory
54169 2018-07-02T15:05:44 Z 0^0(#1448) Teleporters (IOI08_teleporters) C++11
75 / 100
 848 ms 55744 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) {
	if (par[x] == x)return x;
	return par[x] = find(par[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());
	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] + m * 2;
	for (int i = 0; i < t.size() && i < m; i++)
		ans += t[t.size() - 1 - i];
	printf("%d\n", ans);
	return 0;
}

Compilation message

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

Subtask #2
5.0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

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

Subtask #9
5.0 / 5.0

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

Subtask #10
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

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

# Verdict Execution time Memory Grader output
1 Incorrect 6 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 10 ms 1384 KB Output is correct

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 7000 KB Output is correct
2 Correct 203 ms 15676 KB Output is correct

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 15676 KB Output is correct
2 Incorrect 316 ms 22768 KB Output isn't correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 33584 KB Output is correct
2 Correct 553 ms 39804 KB Output is correct
3 Correct 572 ms 46512 KB Output is correct

Subtask #19
0 / 5.0

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

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 781 ms 54180 KB Output is correct
2 Correct 842 ms 54576 KB Output is correct
3 Correct 482 ms 55636 KB Output is correct
4 Correct 848 ms 55744 KB Output is correct