#include <bits/stdc++.h>
using namespace std;
void just_do_it();
int main() {
#ifdef KAMIRULEZ
freopen("kamirulez.inp", "r", stdin);
freopen("kamirulez.out", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
just_do_it();
return 0;
}
const int maxn = 1e6 + 20;
pair<int, int> a[maxn * 2];
int adj[maxn * 2];
bool flag[maxn * 2];
int sz = 0;
void dfs(int u) {
flag[u] = true;
sz++;
if (!flag[adj[u]]) {
dfs(adj[u]);
}
}
void just_do_it() {
int n, m;
cin >> n >> m;
n++;
a[1] = make_pair(0, 1);
a[2] = make_pair(maxn * 2, n + 1);
for (int i = 2; i <= n; i++) {
a[i * 2 - 1].second = i;
a[i * 2].second = n + i;
cin >> a[i * 2 - 1].first >> a[i * 2].first;
}
sort(a + 1, a + n * 2 + 1);
for (int i = 1; i <= n * 2 - 1; i++) {
int u = a[i].second;
int v = a[i + 1].second;
if (v > n) {
v -= n;
}
else {
v += n;
}
adj[u] = v;
}
dfs(1);
int res = sz - 1;
vector<int> sizes;
for (int i = 1; i <= n * 2; i++) {
if (i != n + 1 && !flag[i]) {
sz = 0;
dfs(i);
sizes.push_back(sz);
}
}
sort(sizes.begin(), sizes.end(), greater<int>());
for (int i = 0; i < (int)sizes.size() && m > 0; i++) {
res += sizes[i] + 2;
m--;
}
res += 4 * (m / 2) + (m % 2);
cout << res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
5 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
5 ms |
852 KB |
Output is correct |
3 |
Correct |
11 ms |
1364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
4080 KB |
Output is correct |
2 |
Correct |
117 ms |
8852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
81 ms |
6568 KB |
Output is correct |
2 |
Correct |
194 ms |
12568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
249 ms |
18504 KB |
Output is correct |
2 |
Correct |
392 ms |
32456 KB |
Output is correct |
3 |
Correct |
313 ms |
36292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
441 ms |
25076 KB |
Output is correct |
2 |
Correct |
457 ms |
40548 KB |
Output is correct |
3 |
Correct |
444 ms |
39828 KB |
Output is correct |
4 |
Correct |
497 ms |
40216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
530 ms |
30248 KB |
Output is correct |
2 |
Correct |
430 ms |
44492 KB |
Output is correct |
3 |
Correct |
292 ms |
44256 KB |
Output is correct |
4 |
Correct |
401 ms |
44440 KB |
Output is correct |