#include <bits/stdc++.h>
using namespace std;
vector< vector<int> > g;
vector<bool> was;
int sz = 0;
void dfs(int u) {
was[u] = true;
for (auto& v : g[u]) {
sz++;
if (!was[v]) {
dfs(v);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
map<int, int> other;
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(e);
a.push_back(w);
}
sort(a.begin(), a.end());
g.resize(2 * n + 1);
for (int i = 0; i < 2 * n; i++) {
g[i].push_back(upper_bound(a.begin(), a.end(), other[a[i]]) - a.begin());
}
was.assign(2 * n + 1, false);
dfs(0);
int ans = sz;
priority_queue<int> pq;
for (int i = 0; i <= 2 * n; i++) {
if (!was[i]) {
sz = 0;
dfs(i);
pq.push(sz);
}
}
while (m > 0 && !pq.empty()) {
ans += pq.top() + 2;
pq.pop();
m--;
}
while (m > 0) {
ans++;
m--;
if (m > 0) {
ans += 3;
m--;
}
}
cout << ans + m << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
1152 KB |
Output is correct |
2 |
Correct |
16 ms |
2816 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
1664 KB |
Output is correct |
2 |
Correct |
23 ms |
3192 KB |
Output is correct |
3 |
Correct |
54 ms |
8952 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
3968 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
4604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
330 ms |
31932 KB |
Output is correct |
2 |
Runtime error |
722 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
521 ms |
51560 KB |
Output is correct |
2 |
Runtime error |
938 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1042 ms |
61152 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1085 ms |
65536 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1093 ms |
61020 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |