#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
set<int> point;
int p[2*N];
int sz[2*N];
int mark[2*N];
pair<int,int> tele[N];
bool exist[2*N];
int nxt[2*N];
priority_queue<int> pq;
int fin(int i){
if(p[i]==i) return i;
return p[i] = fin(p[i]);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,m,mn=1e9;
cin >> n >> m;
for(int i=0;i<n;i++){
cin >> tele[i].first >> tele[i].second;
mn = min(mn,tele[i].first);
exist[tele[i].first] = exist[tele[i].second] = true;
sz[tele[i].first] = sz[tele[i].second] = 1;
p[tele[i].first] = tele[i].first;
p[tele[i].second] = tele[i].second;
}
int prev = mn;
for(int i=mn+1;i<=2000000;i++){
if(exist[i]) nxt[prev] = i,prev=i;
}
for(int i=0;i<n;i++){
int next = nxt[tele[i].second];
if(next!=0&&fin(next)!=fin(tele[i].first)){
sz[fin(tele[i].first)]+=sz[fin(next)];
p[fin(next)] = fin(tele[i].first);
}
next = nxt[tele[i].first];
if(next!=0&&fin(next)!=fin(tele[i].second)){
sz[fin(tele[i].second)]+=sz[fin(next)];
p[fin(next)] = fin(tele[i].second);
}
}
int ans = sz[fin(mn)];
mark[fin(mn)] = true;
for(int i=1;i<=2000000;i++){
if(!exist[i]||mark[fin(i)]) continue;
pq.push(sz[fin(i)]);
mark[fin(i)] = true;
}
while(!pq.empty()&&m){
ans+=pq.top()+2;
pq.pop();
--m;
}
cout << ans+2*m-(m%2) << "\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
372 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
596 KB |
Output is correct |
2 |
Correct |
12 ms |
1364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
684 KB |
Output is correct |
2 |
Correct |
10 ms |
2260 KB |
Output is correct |
3 |
Correct |
11 ms |
1364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
852 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
1044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
73 ms |
9924 KB |
Output is correct |
2 |
Correct |
211 ms |
30620 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
130 ms |
22980 KB |
Output is correct |
2 |
Correct |
327 ms |
37708 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
374 ms |
40296 KB |
Output is correct |
2 |
Correct |
398 ms |
41540 KB |
Output is correct |
3 |
Correct |
389 ms |
37312 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
696 ms |
41904 KB |
Output is correct |
2 |
Correct |
603 ms |
43040 KB |
Output is correct |
3 |
Correct |
573 ms |
33484 KB |
Output is correct |
4 |
Correct |
562 ms |
33464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
636 ms |
44500 KB |
Output is correct |
2 |
Correct |
580 ms |
44292 KB |
Output is correct |
3 |
Correct |
346 ms |
41504 KB |
Output is correct |
4 |
Correct |
494 ms |
45408 KB |
Output is correct |