Submission #555610

#	Time	Username	Problem	Language	Result	Execution time	Memory
555610		alextodoran	Teleporters (IOI08_teleporters)	C++17	100 / 100	339 ms	30936 KiB

teleporters

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int X_MAX = 2000000;

int N, M;

int to[X_MAX + 2];
bool tel[X_MAX + 2];

bool seen[X_MAX + 2];
int dfs (int s) {
    int u = s;
    int cnt = 0;
    do {
        cnt += tel[u];
        seen[u] = true;
        u = to[u];
    } while (u != X_MAX + 1 && u != s);
    return cnt;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    for (int u = 0; u <= X_MAX; u++) {
        to[u] = u + 1;
    }
    for (int i = 1; i <= N; i++) {
        int u, v;
        cin >> u >> v;
        to[u - 1] = v; tel[u - 1] = true;
        to[v - 1] = u; tel[v - 1] = true;
    }

    vector <int> v;
    for (int u = 0; u <= X_MAX; u++) {
        if (seen[u] == false) {
            v.push_back(dfs(u));
        }
    }
    sort(v.begin() + 1, v.end(), greater <int> ());
    int score = v.front();
    int join = min((int) v.size() - 1, M);
    M -= join;
    for (int i = 1; i <= join; i++) {
        score += 2 + v[i];
    }
    score += (M / 2) * (1 + 3);
    score += (M % 2) * 1;
    cout << score << "\n";

    return 0;
}

• 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