#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
int n, m, a[maxn], b[maxn], novi[maxn * 2];
int ans, bio[maxn * 2];
vector <int> ciklusi, v;
int sus[maxn * 2];
int dfs (int x){
if (bio[sus[x]] == -1){
bio[sus[x]] = bio[x] + 1;
return dfs(sus[x]);
}
return bio[x];
}
int main (void){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; i++){
cin >> a[i] >> b[i];
v.push_back(a[i]);
v.push_back(b[i]);
}
sort(v.begin(), v.end());
for (int i = 0; i < v.size(); i++){
novi[v[i]] = i;
}
for (int i = 0; i < n; i++){
a[i] = novi[a[i]];
b[i] = novi[b[i]];
sus[a[i]] = b[i] + 1;
}
memset(bio, -1, sizeof bio);
for (int i = 0; i < 2 * n; i++){
if (bio[i] == -1){
bio[i] = 0;
int len = dfs(i);
//cout << i << " " << len << endl;
if (i == 0) ans = len;
else ciklusi.push_back(len + 1);
}
}
sort(ciklusi.begin(), ciklusi.end());
reverse(ciklusi.begin(), ciklusi.end());
int br = 0;
while (m > 0 and br < ciklusi.size()){
ans += ciklusi[br] + 2;
br++;
m--;
}
ans += (m / 2) * 4;
if (m % 2 == 1) ans++;
cout << ans << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |