#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
int n, m;
int s[1000000];
int e[1000000];
int comp[2000000];
int to[2000000];
bool visited[2000001];
int arr[2000000];
int find(int x) {
return lower_bound(comp, comp + (n << 1 | 1), x) - comp;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> s[i] >> e[i];
comp[i << 1 | 0] = s[i];
comp[i << 1 | 1] = e[i];
}
comp[n << 1] = 0;
sort(comp, comp + (n << 1 | 1));
for (int i = 0; i < n; ++i) {
s[i] = find(s[i]);
e[i] = find(e[i]);
to[s[i]] = e[i];
to[e[i]] = s[i];
}
visited[n << 1] = 1;
int j = 0;
for (int i = 0; i < (n << 1); ++i) {
if (visited[i]) continue;
int x = to[i + 1];
visited[i] = 1;
arr[j] = 1;
while (!visited[x]) {
visited[x] = 1;
x = to[x + 1];
++arr[j];
}
++j;
}
int sz = arr[0];
sort(arr + 1, arr + j, greater<int>());
for (int i = 1; i < j && m > 0; ++i, --m) {
sz += arr[i] + 2;
}
printf("%d\n", sz + ((m >> 1) << 2) + (m & 1));
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
560 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
560 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
560 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
560 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
560 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
560 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
560 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
592 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
724 KB |
Output is correct |
2 |
Correct |
9 ms |
968 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
968 KB |
Output is correct |
2 |
Correct |
11 ms |
996 KB |
Output is correct |
3 |
Correct |
19 ms |
1384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
1384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
1384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
96 ms |
4024 KB |
Output is correct |
2 |
Correct |
277 ms |
8664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
166 ms |
8664 KB |
Output is correct |
2 |
Correct |
416 ms |
12524 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
632 ms |
18316 KB |
Output is correct |
2 |
Correct |
676 ms |
21612 KB |
Output is correct |
3 |
Correct |
708 ms |
24700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
853 ms |
24700 KB |
Output is correct |
2 |
Correct |
925 ms |
26780 KB |
Output is correct |
3 |
Correct |
868 ms |
26780 KB |
Output is correct |
4 |
Correct |
858 ms |
26780 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1068 ms |
28668 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |