제출 #1369867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1369867		hirayuu_oj	Teleporters (IOI08_teleporters)	C++20	100 / 100	126 ms	20312 KiB

teleporters

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define each(i,x) for(auto i:x)
#define all(x) x.begin(),x.end()
using ll=long long;
#define fi first
#define se second
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;cin>>N;
    int M;cin>>M;
    int X=2000001;
    vector<int> p(X,-1);
    rep(i,N){
        int W,E;cin>>W>>E;
        p[W]=E;
        p[E]=W;
    }
    int ans=0;
    vector<int> c;
    vector<int> vis(X,0);
    rep(i,X){
        if(vis[i])continue;
        vis[i]=1;
        int cnt=0;
        int ps=i;
        while(ps<X){
            if(p[ps]!=-1){
                ps=p[ps];
                cnt++;
            }
            ps++;
            if(vis[ps])break;
            vis[ps]=1;
        }
        if(i==0)ans=cnt;
        else c.push_back(cnt);
    }
    sort(all(c));
    while(M>0&&!c.empty()){
        ans+=c.back()+2;
        c.pop_back();M--;
    }
    while(M>=2){
        ans+=4;M-=2;
    }
    if(M)ans++;
    cout<<ans<<"\n";
}

• 서브태스크 1: 5 / 5
• 서브태스크 2: 5 / 5
• 서브태스크 3: 5 / 5
• 서브태스크 4: 5 / 5
• 서브태스크 5: 5 / 5
• 서브태스크 6: 5 / 5
• 서브태스크 7: 5 / 5
• 서브태스크 8: 5 / 5
• 서브태스크 9: 5 / 5
• 서브태스크 10: 5 / 5
• 서브태스크 11: 5 / 5
• 서브태스크 12: 5 / 5
• 서브태스크 13: 5 / 5
• 서브태스크 14: 5 / 5
• 서브태스크 15: 5 / 5
• 서브태스크 16: 5 / 5
• 서브태스크 17: 5 / 5
• 서브태스크 18: 5 / 5
• 서브태스크 19: 5 / 5
• 서브태스크 20: 5 / 5