#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 8000005;
const int inf=1000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
int n,m;
bool vis[MAXN];
vector<int>cycs;
int to[MAXN];
int SZ;
int init;
int cnter;
void dfs(int x, int head){
if(vis[x]){
cycs.push_back(SZ);
SZ=0;
return;
}
vis[x]=1;
if(x==8*n+1){
init=SZ;
SZ=0;
return;
}
if(to[x]!=-1){
++SZ;
dfs(to[x],head);
} else{
dfs(x+1,head);
}
}
map<int,int> mper;
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
memset(to,-1,sizeof to);
vector<pi>in;
vector<int>disc;
for(int i=1;i<=n;i++){
int a,b; cin >> a >> b;
in.push_back({a,b});
disc.push_back(a);
disc.push_back(b);
}
sort(disc.begin(),disc.end());
disc.resize(unique(disc.begin(),disc.end())-disc.begin());
int idx=0;
for(auto x:disc){
mper[x]=2*(++idx);
}
for(auto x:in){
int a=mper[x.first];
int b=mper[x.second];
to[a*2+1]=b*2;
to[b*2-1]=2*(a+1);
}
for(int i=1;i<=8*n;i++){
if(!vis[i])dfs(i,i);
}
sort(cycs.begin(),cycs.end(),greater<int>());
int ans=init;
if((int)cycs.size()>=m){
for(int i=0;i<m;i++){
ans+=2+cycs[i];
}
} else{
for(int i=0;i<(int)cycs.size();i++){
ans+=2+cycs[i];
}
int k=m-(int)cycs.size();
for(int i=0;i<k;i++){
if(i%2==0)ans+=1;
else ans+=3;
}
}
cout<<ans<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
35416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
35420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
35416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
35420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
35416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
35420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
35420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
35420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
35416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
35416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
35420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
35848 KB |
Output is correct |
2 |
Correct |
12 ms |
36696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
35932 KB |
Output is correct |
2 |
Correct |
13 ms |
36952 KB |
Output is correct |
3 |
Correct |
28 ms |
38752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
36956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
37272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
144 ms |
49516 KB |
Output is correct |
2 |
Runtime error |
165 ms |
65536 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
291 ms |
59312 KB |
Output is correct |
2 |
Runtime error |
207 ms |
65536 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
241 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
337 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
338 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |