#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define rep(a) for(int i = 0; i < a; i++)
#define each(i,a) for(auto&& i : a)
#define all(a) begin(a), end(a)
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<pii> a(n);
vector<int> x;
each(i, a){
int a, b;
cin >> a >> b;
i = {a, b};
x.push_back(a);
x.push_back(b);
}
sort(all(x));
x.erase(unique(all(x)), x.end());
vector<int> to(n * 2);
each(i, a){
i.first = lower_bound(all(x), i.first) - x.begin();
i.second = lower_bound(all(x), i.second) - x.begin();
to[i.first] = i.second;
to[i.second] = i.first;
}
vector<int> color(n * 2, -1), cnt;
int at = 0, c = 0, ans = 0;
while(at != n * 2){
color[at] = c;
ans++;
at = to[at] + 1;
}
rep(n * 2) if(color[i] == -1){
cnt.push_back(0);
int at = i; c++;
while(at != n * 2 && color[at] == -1){
color[at] = c;
cnt.back()++;
at = to[at] + 1;
}
}
sort(all(cnt));
while(cnt.size() && m){
ans += cnt.back() + 2;
cnt.pop_back();
m--;
}
ans += m / 2 * 4 + m % 2;
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
512 KB |
Output is correct |
2 |
Correct |
10 ms |
820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
512 KB |
Output is correct |
2 |
Correct |
12 ms |
1020 KB |
Output is correct |
3 |
Correct |
23 ms |
1792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
1152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
6488 KB |
Output is correct |
2 |
Correct |
241 ms |
15052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
165 ms |
10860 KB |
Output is correct |
2 |
Correct |
398 ms |
22000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
549 ms |
32600 KB |
Output is correct |
2 |
Correct |
671 ms |
38744 KB |
Output is correct |
3 |
Correct |
714 ms |
45144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
866 ms |
44200 KB |
Output is correct |
2 |
Correct |
923 ms |
48088 KB |
Output is correct |
3 |
Correct |
863 ms |
45784 KB |
Output is correct |
4 |
Correct |
885 ms |
46376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
975 ms |
52820 KB |
Output is correct |
2 |
Correct |
970 ms |
53080 KB |
Output is correct |
3 |
Correct |
514 ms |
54248 KB |
Output is correct |
4 |
Correct |
899 ms |
54176 KB |
Output is correct |