Submission #1287132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287132		BlockOG	Teleporters (IOI08_teleporters)	C++20	100 / 100	228 ms	16148 KiB

teleporters

#include <bits/stdc++.h>

// mrrrow meeow :3
// go play vivid/stasis now! https://vividstasis.gay

#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;

int ____init = [] {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

int conn[2000002];
int vis[2000003];
int sort1[4000001];

int main() {
    int n, m; cin >> n >> m;
    fo(i, 0, n) {
        int a, b; cin >> a >> b;
        conn[a] = b, conn[b] = a;
    }

    vis[2000002] = true;

    int res = 0;
    for (int j = 0; !vis[j];) {
        vis[j] = true;
        if (conn[j + 1]) j = conn[j + 1], res++; else j++;
    }

    fo(i, 1, 2000001) {
        if (vis[i]) continue;

        int conns = 0;
        for (int j = i; !vis[j];) {
            vis[j] = true;
            if (conn[j + 1]) j = conn[j + 1], conns++; else j++;
        }
        sort1[conns]++;
    }

    of(i, 1, 4000001) {
        while (m && sort1[i]) sort1[i]--, m--, res += 2 + i;
        if (!m) break;
    }

    cout << res + (m + 1) / 2 + m / 2 * 3;
}

• 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