#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];
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 << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
15956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
15916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
15956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
15956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
15956 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
14 ms |
15956 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
15992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
15916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
16004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
15956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
15928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
16300 KB |
Output is correct |
2 |
Correct |
31 ms |
17348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
16 ms |
16468 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
17584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
18064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
310 ms |
33176 KB |
Output is correct |
2 |
Execution timed out |
1037 ms |
59416 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
653 ms |
46876 KB |
Output is correct |
2 |
Execution timed out |
1084 ms |
65536 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
975 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
980 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
936 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |