#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int) 2e6;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> other(MAXN + 1, -1);
vector<int> a;
for (int i = 0; i < n; i++) {
int w, e;
cin >> w >> e;
other[w] = e; other[e] = w;
a.push_back(w); a.push_back(e);
}
sort(a.begin(), a.end());
vector<int> next(2 * n + 1, -1);
for (int i = 0; i < 2 * n; i++) {
next[i] = upper_bound(a.begin(), a.end(), other[a[i]]) - a.begin();
}
vector<bool> was(2 * n + 1, false); was[0] = true;
queue<int> q; q.push(0);
int ans = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
if (next[u] != -1 && !was[next[u]]) {
ans++;
q.push(next[u]);
was[next[u]] = true;
}
}
vector<int> b;
for (int i = 0; i < 2 * n; i++) {
if (was[i]) {
continue;
}
q.push(i);
was[i] = true;
b.push_back(0);
while (!q.empty()) {
int u = q.front(); q.pop();
b.back()++;
if (next[u] != -1 && !was[next[u]]) {
q.push(next[u]);
was[next[u]] = true;
}
}
}
sort(b.rbegin(), b.rend());
for (int i = 0; i < min((int) b.size(), m); i++) {
ans += b[i] + 2;
}
m -= min((int) b.size(), m);
ans += (m + 1) / 2 + (m / 2) * 3;
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
8192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
8192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
8192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8192 KB |
Output is correct |
2 |
Correct |
12 ms |
8448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8192 KB |
Output is correct |
2 |
Correct |
16 ms |
8448 KB |
Output is correct |
3 |
Correct |
21 ms |
8832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
8448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
8576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
87 ms |
10752 KB |
Output is correct |
2 |
Correct |
230 ms |
13996 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
145 ms |
12396 KB |
Output is correct |
2 |
Correct |
351 ms |
16368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
434 ms |
29144 KB |
Output is correct |
2 |
Correct |
567 ms |
35160 KB |
Output is correct |
3 |
Correct |
516 ms |
40408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
729 ms |
30440 KB |
Output is correct |
2 |
Correct |
751 ms |
41172 KB |
Output is correct |
3 |
Correct |
621 ms |
38244 KB |
Output is correct |
4 |
Correct |
652 ms |
38908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
862 ms |
43076 KB |
Output is correct |
2 |
Correct |
779 ms |
45684 KB |
Output is correct |
3 |
Correct |
504 ms |
46956 KB |
Output is correct |
4 |
Correct |
625 ms |
46796 KB |
Output is correct |