(IOI) 2008 Day 2 p3 Teleporters

https://contest.yandex.com/ioi/contest/567/problems/F/

超精湛的一題(?)

我們先把線段分成2N + 1塊，然後每次的teleport 就把兩個interval連在一起的感覺。

這樣一來，我們就得到很多連通塊了。

我們可以加M個新線段，每加一條新的線段時，可以：

(1) merge  兩個連通塊，並且讓那個連通塊多兩分。
(2) 在一個連通塊產生一個新的連通塊(分數為1)，原本的連通塊分數也加1。
(3) 忘了，editorial裡面有寫><

只需要用到前面兩個喔~

複雜度：O(N+M + 排序)

#include <bits/stdc++.h>
using namespace std;

const int N = 2000002;

bitset<N> vis;

int has_port[N];
int e[N];

int cnt=0;

void dfs(int now)
{
    if (vis[now] || now == N-1) return;
    vis[now] = true;
    if (has_port[now])
    {
        ++cnt;
        int _ = now, __ = ( e[ has_port[now] ]^now );
        if (_ > __) swap(_,__);
        if (now == __) dfs(_+1);
        if (now == _) dfs(__+1);
    }
    else
    {
        dfs(now+1);
    }
}

int main ()
{
    int n;
    scanf("%d",&n);
    int m;
    scanf("%d",&m);
    for (int i=1;n>=i;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        e[i] = (x^y);
        has_port[x] = i;
        has_port[y] = i;
    }
    vector<int> v;
    int start = -1;
    for (int i=1;N>i;i++)
    {
        if (!vis[i])
        {
            cnt = 0;
            dfs(i);
            if (i == 1) start = cnt;
            else if (cnt) v.push_back(cnt);
        }
    }
    if (v.size() >= m)
    {
        sort(v.begin(),v.end());
        reverse(v.begin(),v.end());
        int ans=start;
        for (int i=0;m>i;i++)
        {
            ans += (v[i]+2);
        }
        printf("%d\n",ans);
    }
    else
    {
        int ans=start;
        for (int i:v)
        {
            ans += (i+2);
            --m;
        }
        if (m%2==0) ans += 2*m;
        else ans += 2*m-1;
        printf("%d\n",ans);
    }
}