Submission #601322

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
601322	2022-07-21T17:05:20 Z	Ozy	Teleporters (IOI08_teleporters)	C++17	100 / 100	714 ms	42668 KB

teleporters

#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>

#define debugsl(x) std::cout << #x << " = " << x << ", "
#define debug(x) debugsl(x) << "\n";

#define MAX 1000000
#define MAXP 2000001

int n, m, l, r, c, d, pos, res, pareja[MAXP + 2], ciclo[MAXP + 2], tam[MAXP + 2];
std::vector<int> ciclosPorTamano;

int main() {

    std::cin >> n >> m;
    std::iota(pareja, pareja + MAXP + 1, 1);
    for(int i = 1; i <= n; ++i){
        std::cin >> l >> r;

        // PARA CADA POSICION CONFIGURA COMO SU PAREJA LA POSICION
        // DONDE ESTA EL OTRO EXTREMO DEL PORTAL
        pareja[l - 1] = r;
        pareja[r - 1] = l;
    }

    // VALIDA LOS CICLOS CON UNA ESTRUCTURA TIPO UNION FIND.
    // INICIALIZA LA ESTRUCTURA
    std::fill(tam, tam + MAXP + 1, 0);
    std::iota(ciclo, ciclo + MAXP + 1, 0);

    for(int i = 0; i <= MAXP; ++i){
        if (ciclo[i] == i){
            c = i;
            pos = pareja[i];
            ciclo[pos] = c;

            if (pos != c + 1) ++tam[c];
            while (pos < MAXP && pos != c){
                if (pareja[pos] == pos + 1){
                    pos = pos + 1;
                    ciclo[pos] = c;
                }
                else{
                    pos = pareja[pos];
                    ciclo[pos] = c;
                    ++tam[c];
                }
            }

            // EL C ES UN CAMINO, NO UN CICLO, NO HAY QUE AGREGARLO
            if (c) ciclosPorTamano.push_back(c);
        }
    }

    // ORDENA LOS CICLOS POR TAMANO
    std::sort(ciclosPorTamano.begin(), ciclosPorTamano.end(), [&](int a, int b){return tam[a] > tam[b];});

    res = tam[0];
    d = m - ciclosPorTamano.size();
    if (d > 0){
        res += (d >> 1) << 2;
        res += d & 1;
    }
    for(int i = 0; i < std::min(m, (int)ciclosPorTamano.size()); ++i) res += tam[ciclosPorTamano[i]] + 2;

    std::cout << res << "\n";

    return 0;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	23784 KB	Output is correct

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	23732 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23788 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23764 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	23736 KB	Output is correct

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23764 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	23788 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	23712 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23676 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	23764 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	23768 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	23844 KB	Output is correct
2	Correct	18 ms	23892 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	23804 KB	Output is correct
2	Correct	24 ms	23920 KB	Output is correct
3	Correct	34 ms	24008 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	23892 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	23940 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	88 ms	25788 KB	Output is correct
2	Correct	253 ms	28708 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	198 ms	27292 KB	Output is correct
2	Correct	325 ms	30896 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	467 ms	34976 KB	Output is correct
2	Correct	526 ms	36896 KB	Output is correct
3	Correct	549 ms	39712 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	608 ms	38704 KB	Output is correct
2	Correct	684 ms	39744 KB	Output is correct
3	Correct	639 ms	38076 KB	Output is correct
4	Correct	649 ms	38300 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	683 ms	42472 KB	Output is correct
2	Correct	714 ms	42548 KB	Output is correct
3	Correct	626 ms	42668 KB	Output is correct
4	Correct	697 ms	42512 KB	Output is correct

Submission #601322

Compilation message