#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+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];
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=1;i<=2000000;i++) sz[i] = 1,p[i] = i;
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;
point.insert(tele[i].first);
point.insert(tele[i].second);
}
for(int i=0;i<n;i++){
auto nxt = point.upper_bound(tele[i].second);
if(nxt!=point.end()&&fin(*nxt)!=fin(tele[i].first)){
sz[fin(tele[i].first)]+=sz[fin(*nxt)];
p[fin(*nxt)] = fin(tele[i].first);
}
nxt = point.upper_bound(tele[i].first);
if(nxt!=point.end()&&fin(*nxt)!=fin(tele[i].second)){
sz[fin(tele[i].second)]+=sz[fin(*nxt)];
p[fin(*nxt)] = 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 |
11 ms |
15956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
15992 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
15964 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
15956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
15960 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
15956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
15956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
15956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
15916 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
15956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
16044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
16340 KB |
Output is correct |
2 |
Correct |
21 ms |
17236 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
16416 KB |
Output is correct |
2 |
Correct |
27 ms |
17932 KB |
Output is correct |
3 |
Correct |
47 ms |
19404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
17352 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
32 ms |
17948 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
265 ms |
31424 KB |
Output is correct |
2 |
Correct |
918 ms |
55152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
560 ms |
43952 KB |
Output is correct |
2 |
Execution timed out |
1090 ms |
65536 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
809 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
850 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
798 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |