# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1020825 | boyliguanhan | Teleporters (IOI08_teleporters) | C++17 | 583 ms | 28316 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
int go[2000100],tele[2000100],st[2000100],sz;
bitset<2000100>vis;
int docycle(int n){
int x=0;
while(!vis[n])
x++,vis[n]=1,n=go[n];
return x;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
tele[x]=y;
tele[y]=x;
st[sz++]=x;
st[sz++]=y;
}
sz++;
st[sz++]=2e6+1;
tele[(int)2e6+1]=2e6+1;
sort(st,st+sz);
for(int i=0;i<sz;i++){
if(st[i]>2e6)break;
go[st[i]]=tele[st[i+1]];
}
int x=0,y=0;
while(x<=2e6)
y++,vis[x]=1,x=go[x];
priority_queue<int>pq;
for(int i=0;i<sz;i++)
if(!vis[st[i]])
pq.push(docycle(st[i]));
if(m>=pq.size())
cout<<(n+m)*2-(n+m&1);
else {
while(m--)
y+=2+pq.top(),pq.pop();
cout<<y-1;
}
}
Compilation message (stderr)
# | 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... |