#include <iostream>
#include <algorithm>
#include <vector>
const int MAXN = 2e6 + 2;
int warp[MAXN], next[MAXN];
bool seen[MAXN];
std::vector<int> cycleSizes;
int floodfill(int pos)
{
if (seen[pos])
return 0;
seen[pos] = true;
return (floodfill(warp[next[pos]]) + 1);
}
int main()
{
std::ios::sync_with_stdio(false);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
std::fill_n(warp, MAXN, -1);
warp[0] = 0;
warp[MAXN - 1] = MAXN - 1;
int teleporters, canAdd;
std::cin >> teleporters >> canAdd;
for (int iTel = 0; iTel < teleporters; iTel++)
{
int west, east;
std::cin >> west >> east;
warp[west] = east;
warp[east] = west;
}
int lastSeen = MAXN - 1;
next[MAXN - 1] = MAXN - 1;
for (int iPos = MAXN - 2; iPos > -1; iPos--)
if (warp[iPos] != -1)
{
next[iPos] = lastSeen;
lastSeen = iPos;
}
int score = floodfill(0) - 2;
for (int iPos = 1; iPos < MAXN - 1; iPos++)
if (!seen[iPos] && warp[iPos] != -1)
cycleSizes.emplace_back(floodfill(iPos));
std::sort(cycleSizes.rbegin(), cycleSizes.rend());
for (int iCyc = 0; iCyc < (int)cycleSizes.size() && canAdd > 0; iCyc++)
{
score += cycleSizes[iCyc] + 2;
canAdd--;
}
std::cout << score + canAdd * 2 - canAdd % 2 << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
8184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
8184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
8188 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
8184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
8184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
8184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
8184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
8184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
8220 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
8184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
8184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
8312 KB |
Output is correct |
2 |
Correct |
18 ms |
8568 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
8312 KB |
Output is correct |
2 |
Correct |
20 ms |
8924 KB |
Output is correct |
3 |
Correct |
22 ms |
8824 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
8440 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
8568 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
69 ms |
12672 KB |
Output is correct |
2 |
Correct |
221 ms |
21188 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
144 ms |
17780 KB |
Output is correct |
2 |
Correct |
312 ms |
25224 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
350 ms |
29172 KB |
Output is correct |
2 |
Correct |
370 ms |
29084 KB |
Output is correct |
3 |
Correct |
330 ms |
29160 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
458 ms |
27936 KB |
Output is correct |
2 |
Correct |
474 ms |
27904 KB |
Output is correct |
3 |
Correct |
384 ms |
25720 KB |
Output is correct |
4 |
Correct |
394 ms |
25596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
475 ms |
29396 KB |
Output is correct |
2 |
Correct |
465 ms |
29688 KB |
Output is correct |
3 |
Correct |
284 ms |
29496 KB |
Output is correct |
4 |
Correct |
403 ms |
29560 KB |
Output is correct |