//by atodo
/**
____ ____ ____ ____ ____
||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 |
10068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
10060 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
10060 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
10068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
10044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
10064 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
10092 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
10080 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
10104 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
10056 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
10100 KB |
Output is correct |
2 |
Correct |
14 ms |
10324 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
10092 KB |
Output is correct |
2 |
Correct |
18 ms |
10364 KB |
Output is correct |
3 |
Correct |
22 ms |
10496 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
10200 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
10324 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
40 ms |
11564 KB |
Output is correct |
2 |
Correct |
108 ms |
12844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
74 ms |
12496 KB |
Output is correct |
2 |
Correct |
146 ms |
13024 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
195 ms |
14424 KB |
Output is correct |
2 |
Correct |
232 ms |
14476 KB |
Output is correct |
3 |
Correct |
226 ms |
16200 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
257 ms |
14664 KB |
Output is correct |
2 |
Correct |
302 ms |
14484 KB |
Output is correct |
3 |
Correct |
240 ms |
12324 KB |
Output is correct |
4 |
Correct |
283 ms |
12328 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
304 ms |
16536 KB |
Output is correct |
2 |
Correct |
289 ms |
16620 KB |
Output is correct |
3 |
Correct |
195 ms |
16576 KB |
Output is correct |
4 |
Correct |
312 ms |
16672 KB |
Output is correct |