#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define all(x) begin(x),end(x)
/*
Idea:
traverse without any added
enumerate and group up unreachable regions
need only count of number of teles in each region
only 2(teleporters)+1 states, changing takes exactly one teleport => optimal 2(n+m) points
any new teleporter added can only increase region count by 2, and should ideally connect a reachable and unreachable
section together (this makes the unreachable section a "subroutine" at the other point)
*/
// adding each teleporter:
// if both endpoints are the same group, partition the group into "inside" and "outside"
// if enpoints are different, the ends become the same group
// sounds like union find
// size of the path. Made smaller for debugging purposes. Should be strictly bigger than the last paths end.
#define PATHLEN 2000010
signed main()
{
int N,M;
cin >> N >> M;
vector<pair<int,int>> tele(N);
for(int i = 0; i < N; i++) cin >> tele[i].first >> tele[i].second;
// sorting the teleporters
vector<int> to(PATHLEN,-1);
for(auto i : tele) {to[i.first] = i.second;to[i.second] = i.first;}
int c = 0;
to.back() = 0;
// tele contains now both ways, sorted by entrance -> exit. Though using to is more useful.
vector<bool> group(PATHLEN,0);
vector<int> gcs;
for(int start = 0; start < PATHLEN; start++)
{
if(group[start]) continue;
int gc = 0;
int i = start;
while(!group[i])
{
group[i] = true;
if(to[i]==-1) {i++; continue;}
i = to[i]+1;
gc++;
}
gcs.push_back(gc);
}
i64 sum_count = 0;
if(M <= gcs.size()-1)
{
// group 0 is the one we start with.
sum_count = gcs[0]-1;
//sort(all(gcs)); // this can be problematic if ie all the paths are disjoint, giving 1e6 different groups
// counting sort to the rescue again!
vector<int> count(2*PATHLEN,0);
for(auto i : gcs) count[i]++;
// make the longest M groups accessible
count[gcs[0]]--; // don't count the original path
for(int i = count.size()-1; M > 0; i--)
{
if(!count[i]) continue;
sum_count += i+2;
count[i]--;
i++;
M--;
}
}
else
{
// include all closed off paths
for(auto i : gcs) sum_count += i+2; // +1 for going into (and out) of the group
sum_count -= 3; // a little overcounting for the first group
M -= gcs.size()-1;
// adding two teleporters adds four
sum_count += 4*(M/2);
if(M%2) sum_count++;
}
cout << sum_count << "\n";
}
Compilation message
teleporters.cpp: In function 'int main()':
teleporters.cpp:54:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | if(M <= gcs.size()-1)
| ~~^~~~~~~~~~~~~~~
teleporters.cpp:34:9: warning: unused variable 'c' [-Wunused-variable]
34 | int c = 0;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
23976 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
24008 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
24048 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
24020 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
8276 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
8276 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
8392 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
24004 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
24020 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
24020 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
8396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
8440 KB |
Output is correct |
2 |
Correct |
22 ms |
24168 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
8404 KB |
Output is correct |
2 |
Correct |
23 ms |
24328 KB |
Output is correct |
3 |
Correct |
20 ms |
8952 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
8532 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
24304 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
74 ms |
26988 KB |
Output is correct |
2 |
Correct |
169 ms |
31164 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
105 ms |
13576 KB |
Output is correct |
2 |
Correct |
221 ms |
19012 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
329 ms |
24460 KB |
Output is correct |
2 |
Correct |
380 ms |
42920 KB |
Output is correct |
3 |
Correct |
406 ms |
45472 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
412 ms |
30208 KB |
Output is correct |
2 |
Correct |
452 ms |
47400 KB |
Output is correct |
3 |
Correct |
461 ms |
30428 KB |
Output is correct |
4 |
Correct |
461 ms |
46376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
491 ms |
35096 KB |
Output is correct |
2 |
Correct |
476 ms |
49244 KB |
Output is correct |
3 |
Correct |
503 ms |
50476 KB |
Output is correct |
4 |
Correct |
477 ms |
50472 KB |
Output is correct |