Submission #963876

#	Time	Username	Problem	Language	Result	Execution time	Memory
963876		fzyzzz_z	Teleporters (IOI08_teleporters)	C++17	100 / 100	467 ms	55292 KiB

teleporters

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define all(x) x.begin(),x.end()
using ll=long long;
const ll INF=(1LL<<60)-1;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,M;
    cin>>N>>M;
    vector<pair<int,int>> pos(N*2);
    rep(i,N){
        int W,E;
        cin>>W>>E;
        pos[i*2]={W,i};
        pos[i*2+1]={E,i};
    }
    sort(all(pos));
    vector<pair<int,int>> tel(N,{-1,-1});
    rep(i,N*2){
        if(tel[pos[i].second].first==-1){
            tel[pos[i].second].first=i;
        }
        else{
            tel[pos[i].second].second=i;
        }
    }
    vector<bool> vis(N*2,0);
    int ans=0;
    vector<int> more;
    rep(i,N*2){
        if(vis[i])continue;
        int now=i;
        int score=0;
        while(!vis[now]){
            vis[now]=1;
            if(tel[pos[now].second].first==now){
                now=tel[pos[now].second].second;
            }
            else{
                now=tel[pos[now].second].first;
            }
            score++;
            now++;
            if(now==N*2)break;
        }
        if(i==0)ans=score;
        else more.emplace_back(score);
    }
    sort(more.rbegin(),more.rend());
    rep(i,M){
        more.emplace_back(-1);
        more.emplace_back(1);
        ans+=more[i];
        ans+=2;
    }
    cout<<ans<<endl;
}

• 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