#include <bits/stdc++.h>
using namespace std;
int n, m;
vector< vector<int> > g;
vector<bool> was;
int sz = 0;
map<int, int> other;
vector<int> a;
void dfs(int u) {
was[u] = true;
if (u == 2 * n) {
return;
}
sz++;
int next = upper_bound(a.begin(), a.end(), other[a[u]]) - a.begin();
if (!was[next]) {
dfs(next);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
int w, e;
cin >> w >> e;
other[w] = e;
other[e] = w;
a.push_back(e);
a.push_back(w);
}
sort(a.begin(), a.end());
was.assign(2 * n + 1, false);
dfs(0);
int ans = sz;
vector<int> b;
for (int i = 0; i < 2 * n; i++) {
if (!was[i]) {
sz = 0;
dfs(i);
b.push_back(sz);
}
}
sort(b.rbegin(), b.rend());
for (int i = 0; i < min(m, (int) b.size()); i++) {
ans += b[i] + 2;
}
m -= min(m, (int) b.size());
while (m > 0) {
ans++;
m--;
if (m > 0) {
ans += 3;
m--;
}
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
672 KB |
Output is correct |
2 |
Correct |
13 ms |
1536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
768 KB |
Output is correct |
2 |
Correct |
16 ms |
1792 KB |
Output is correct |
3 |
Correct |
39 ms |
3692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
1920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
2304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
328 ms |
15468 KB |
Output is correct |
2 |
Execution timed out |
1057 ms |
36188 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
767 ms |
25700 KB |
Output is correct |
2 |
Execution timed out |
1087 ms |
52536 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1099 ms |
65536 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1098 ms |
65536 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1095 ms |
65536 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |