oj.uz

답안 #688595

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
688595 2023-01-27T19:45:28 Z finn__ Teleporters (IOI08_teleporters) C++17
100 / 100
 567 ms 35068 KB 
#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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #8
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #9
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #10
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #11
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #12
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 5 ms 596 KB Output is correct

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 6 ms 724 KB Output is correct
3 Correct 15 ms 1044 KB Output is correct

Subtask #14
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 596 KB Output is correct

Subtask #15
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 740 KB Output is correct

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 4280 KB Output is correct
2 Correct 188 ms 10080 KB Output is correct

Subtask #17
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 7144 KB Output is correct
2 Correct 262 ms 14484 KB Output is correct

Subtask #18
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 337 ms 21384 KB Output is correct
2 Correct 401 ms 25296 KB Output is correct
3 Correct 394 ms 29268 KB Output is correct

Subtask #19
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 540 ms 29132 KB Output is correct
2 Correct 567 ms 31612 KB Output is correct
3 Correct 458 ms 30520 KB Output is correct
4 Correct 443 ms 30812 KB Output is correct

Subtask #20
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 562 ms 35068 KB Output is correct
2 Correct 555 ms 35036 KB Output is correct
3 Correct 401 ms 35032 KB Output is correct
4 Correct 480 ms 35040 KB Output is correct