Submission #556763

#	Time	Username	Problem	Language	Result	Execution time	Memory
556763		jangwonyoung	Teleporters (IOI08_teleporters)	C++14	100 / 100	312 ms	16672 KiB

teleporters

//by atodo
/**
 ____ ____ ____ ____ ____
||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