/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int X_MAX = 2000000;
int N, M;
int to[X_MAX + 2];
bool tel[X_MAX + 2];
bool seen[X_MAX + 2];
int dfs (int s) {
int u = s;
int cnt = 0;
do {
cnt += tel[u];
seen[u] = true;
u = to[u];
} while (u != X_MAX + 1 && u != s);
return cnt;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for (int u = 0; u <= X_MAX; u++) {
to[u] = u + 1;
}
for (int i = 1; i <= N; i++) {
int u, v;
cin >> u >> v;
to[u - 1] = v; tel[u - 1] = true;
to[v - 1] = u; tel[v - 1] = true;
}
vector <int> v;
for (int u = 0; u <= X_MAX; u++) {
if (seen[u] == false) {
v.push_back(dfs(u));
}
}
sort(v.begin() + 1, v.end(), greater <int> ());
int score = v.front();
int join = min((int) v.size() - 1, M);
M -= join;
for (int i = 1; i <= join; i++) {
score += 2 + v[i];
}
score += (M / 2) * (1 + 3);
score += (M % 2) * 1;
cout << score << "\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
10068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
10036 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
10068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
10096 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
10088 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
10068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
10068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
10060 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
10048 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
10060 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
10088 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
10072 KB |
Output is correct |
2 |
Correct |
13 ms |
10292 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
10196 KB |
Output is correct |
2 |
Correct |
17 ms |
10344 KB |
Output is correct |
3 |
Correct |
16 ms |
10452 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
10196 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
10308 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
40 ms |
12608 KB |
Output is correct |
2 |
Correct |
103 ms |
16656 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
74 ms |
14848 KB |
Output is correct |
2 |
Correct |
151 ms |
19208 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
192 ms |
23404 KB |
Output is correct |
2 |
Correct |
226 ms |
25108 KB |
Output is correct |
3 |
Correct |
218 ms |
27660 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
306 ms |
26980 KB |
Output is correct |
2 |
Correct |
333 ms |
28008 KB |
Output is correct |
3 |
Correct |
278 ms |
26476 KB |
Output is correct |
4 |
Correct |
280 ms |
26572 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
339 ms |
30832 KB |
Output is correct |
2 |
Correct |
338 ms |
30936 KB |
Output is correct |
3 |
Correct |
228 ms |
30616 KB |
Output is correct |
4 |
Correct |
311 ms |
30848 KB |
Output is correct |