#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];
int cntSz[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;
cntSz[sz[fin(i)]]++;
mark[fin(i)] = true;
}
for(int i=2000000;i>=1;i--){
while(m&&cntSz[i]) ans+=i+2,--m,--cntSz[i];
}
cout << ans+2*m-(m%2) << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
624 KB |
Output is correct |
2 |
Correct |
8 ms |
1364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
724 KB |
Output is correct |
2 |
Correct |
13 ms |
2272 KB |
Output is correct |
3 |
Correct |
13 ms |
1364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
58 ms |
9508 KB |
Output is correct |
2 |
Correct |
212 ms |
30060 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
123 ms |
22528 KB |
Output is correct |
2 |
Correct |
313 ms |
37004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
335 ms |
38512 KB |
Output is correct |
2 |
Correct |
415 ms |
39516 KB |
Output is correct |
3 |
Correct |
369 ms |
34028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
523 ms |
40620 KB |
Output is correct |
2 |
Correct |
509 ms |
41088 KB |
Output is correct |
3 |
Correct |
503 ms |
33596 KB |
Output is correct |
4 |
Correct |
527 ms |
33712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
518 ms |
41392 KB |
Output is correct |
2 |
Correct |
506 ms |
41460 KB |
Output is correct |
3 |
Correct |
217 ms |
37424 KB |
Output is correct |
4 |
Correct |
428 ms |
41548 KB |
Output is correct |