제출 #1003684

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1003684		bachhoangxuan	Teleporters (IOI08_teleporters)	C++17	100 / 100	189 ms	44636 KiB

teleporters

#include<bits/stdc++.h>
using namespace std;
const int maxa = 2e6;
const int maxn = 1e6+5;
int f[maxa+5],nxt[maxa+5],res=0;
bool vis[maxa+5];

 signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int n,m;cin >> n >> m;
    vector<pair<int,int>> p(n);
    for(int i=0;i<n;i++){
        int x,y;cin >> x >> y;
        f[x]++,f[y]++;
        p[i]={x,y};
    }
    for(int i=1;i<=maxa;i++) f[i]+=f[i-1];
    for(auto [x,y]:p){
        x=f[x],y=f[y];
        nxt[x-1]=y;
        nxt[y-1]=x;
    }
    int N=2*n;
    vector<int> S;
    for(int i=0;i<=N;i++){
        if(!vis[i]){
            int u=i,cnt=0;
            while(!vis[u]) vis[u]=true,cnt++,u=nxt[u];
            if(!i) res+=cnt-1;
            else S.push_back(cnt);
        }
    }
    sort(S.begin(),S.end(),greater<int>());
    for(int x:S){if(m) res+=x+2,m--;}
    for(int i=0;i<m;i++) res+=(i&1)<<1|1;
    cout << res << '\n';
 }

• 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