Submission #688595

#	Time	Username	Problem	Language	Result	Execution time	Memory
688595		finn__	Teleporters (IOI08_teleporters)	C++17	100 / 100	567 ms	35068 KiB

teleporters

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

unsigned get_component_size(
    vector<pair<unsigned, unsigned>> const &teleports, unsigned i,
    vector<bool> &visited)
{
    unsigned j = i;
    unsigned component_size = 0;
    do
    {
        component_size++;
        visited[j] = 1;
        j = upper_bound(teleports.begin(), teleports.end(),
                        make_pair(teleports[j].second, UINT_MAX)) -
            teleports.begin();
    } while (j != i && j < teleports.size());
    return component_size;
}

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

    size_t n, m;
    cin >> n >> m;

    vector<pair<unsigned, unsigned>> teleports(2 * n);
    for (size_t i = 0; i < n; i++)
    {
        unsigned a, b;
        cin >> a >> b;
        teleports[i] = {a, b};
        teleports[n + i] = {b, a};
    }
    sort(teleports.begin(), teleports.end());

    vector<bool> visited(2 * n, 0);
    unsigned ans = get_component_size(teleports, 0, visited);
    vector<unsigned> component_sizes;

    for (size_t i = 0; i < 2 * n; i++)
    {
        if (!visited[i])
        {
            component_sizes.push_back(get_component_size(teleports, i, visited));
        }
    }

    sort(component_sizes.begin(), component_sizes.end());
    while (m--)
    {
        if (!component_sizes.empty())
        {
            ans += component_sizes.back() + 2;
            component_sizes.pop_back();
        }
        else
        {
            ans++;
            component_sizes.push_back(1);
        }
    }

    cout << ans << '\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