Submission #1017772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017772		ttamx	Teleporters (IOI08_teleporters)	C++17	100 / 100	291 ms	29644 KiB

teleporters

#include<bits/stdc++.h>

using namespace std;

const int X=2e6;

int n,m;
pair<int,int> nxt[X+5];
bool vis[X+5];
int ans;
priority_queue<int> pq;

int calc(int x){
    int res=0;
    while(!vis[x]){
        vis[x]=true;
        res+=nxt[x].second;
        x=nxt[x].first;
    }
    return res;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i=1;i<=X;i++)nxt[i]={i+1,0};
    for(int i=0;i<n;i++){
        int l,r;
        cin >> l >> r;
        nxt[l]={r+1,1};
        nxt[r]={l+1,1};
    }
    vis[X+1]=true;
    ans=calc(1);
    for(int i=2;i<=X;i++)if(!vis[i])pq.emplace(calc(i));
    while(!pq.empty()&&m>0){
        ans+=pq.top()+2;
        pq.pop();
        m--;
    }
    cout << ans+m/2*4+m%2;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5