#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e6;
struct Point
{
int x,id;
bool en;
Point(int _x=0,int _id=0,int _en=0) : x(_x),id(_id),en(_en) {};
bool operator<(const Point &oth) const
{
return x<oth.x;
}
};
array<int,2> t[N+10];
bool vis[N+10][2];
set<Point> st;
vector<int> siz;
int dfs(set<Point>::iterator x)
{
int ans=0;
while(x!=st.end() && !vis[(x->id)][(x->en)])
{
vis[(x->id)][(x->en)]=true;
ans++;
x=next(st.find(Point(t[(x->id)][!(x->en)],(x->id),!(x->en))));
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>t[i][0]>>t[i][1];
st.insert(Point(t[i][0],i,0));
st.insert(Point(t[i][1],i,1));
}
int ans=dfs(st.begin());
for(int i=1;i<=n;i++)
{
for(int j:{0,1})
{
if(!vis[i][j])
siz.push_back(dfs(st.find(Point(t[i][j],i,j))));
}
}
sort(siz.begin(),siz.end());
while(m--)
{
if(siz.empty())
{
ans++;
siz.push_back(1);
}
else
{
ans+=2+siz.back();
siz.pop_back();
}
}
cout<<ans<<"\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
716 KB |
Output is correct |
2 |
Correct |
11 ms |
1732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
844 KB |
Output is correct |
2 |
Correct |
14 ms |
2160 KB |
Output is correct |
3 |
Correct |
26 ms |
4676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
2272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
2772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
278 ms |
19248 KB |
Output is correct |
2 |
Correct |
947 ms |
45688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
530 ms |
32408 KB |
Output is correct |
2 |
Execution timed out |
1041 ms |
65536 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
732 ms |
65540 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
797 ms |
65540 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
739 ms |
65540 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |