5720 2023. 09. 09 21:00:26 kukkerman A lehető legkevesebb átszállás (50 pont) cpp17 Elfogadva 50/50 9ms 5720 KiB
#include <iostream>
#include <vector>

void beolvas(std::istream &in, std::vector<std::pair<int, int>> &vonatok, int &allomasok) {
    size_t n;
    in >> n >> allomasok;

    for (auto i = 0u; i < n; i++) {
        int honnan, hova;
        in >> honnan >> hova;
        vonatok.emplace_back(honnan, hova);
    }
}

void feldolgoz(const std::vector<std::pair<int, int>> &vonatok, int allomasok) {
    const auto n = vonatok.size();

    std::vector<int> csatlakozasok(allomasok + 1, -1);
    for (auto i = 0u; i < n; i++) {
        auto [honnan, hova] = vonatok[i];

        if (csatlakozasok[honnan] == -1 || vonatok[csatlakozasok[honnan]].second < hova) {
            csatlakozasok[honnan] = i;
        }
    }

    int akt_vegallomas = 1;
    int atsz_vonat = -1;
    std::vector<int> atszallasok;
    for (auto poz = 1; poz <= allomasok; poz++) {
        if (poz > akt_vegallomas) {
            if (atsz_vonat == -1 || vonatok[atsz_vonat].second < poz) {
                break;
            }

            akt_vegallomas = vonatok[atsz_vonat].second;
            atszallasok.push_back(atsz_vonat);
        }

        if (csatlakozasok[poz] != -1 && (atsz_vonat == -1 || vonatok[atsz_vonat].second < vonatok[csatlakozasok[poz]].second)) {
            atsz_vonat = csatlakozasok[poz];
        }
    }

    if (akt_vegallomas == allomasok) {
        std::cout << atszallasok.size() - 1 << std::endl;
        for (auto v : atszallasok) {
            std::cout << v + 1 << ' ';
        }
        std::cout << std::endl;

    } else {
        std::cout << "-1\n";
    }
}

int main() {
    std::vector<std::pair<int, int>> vonatok;
    int allomasok;

    beolvas(std::cin, vonatok, allomasok);
    feldolgoz(vonatok, allomasok);
    
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1808 KiB
2 Elfogadva 0/0 9ms 3064 KiB
3 Elfogadva 1/1 3ms 2212 KiB
4 Elfogadva 1/1 3ms 2428 KiB
5 Elfogadva 2/2 3ms 2668 KiB
6 Elfogadva 2/2 3ms 2880 KiB
7 Elfogadva 2/2 3ms 3228 KiB
8 Elfogadva 2/2 3ms 3472 KiB
9 Elfogadva 2/2 4ms 3740 KiB
10 Elfogadva 2/2 4ms 3996 KiB
11 Elfogadva 2/2 4ms 4336 KiB
12 Elfogadva 2/2 6ms 4588 KiB
13 Elfogadva 2/2 3ms 4308 KiB
14 Elfogadva 2/2 4ms 4404 KiB
15 Elfogadva 2/2 4ms 4484 KiB
16 Elfogadva 2/2 6ms 4548 KiB
17 Elfogadva 2/2 7ms 4948 KiB
18 Elfogadva 2/2 8ms 4960 KiB
19 Elfogadva 2/2 8ms 5192 KiB
20 Elfogadva 2/2 8ms 5388 KiB
21 Elfogadva 2/2 8ms 5604 KiB
22 Elfogadva 2/2 8ms 5612 KiB
23 Elfogadva 2/2 8ms 5552 KiB
24 Elfogadva 2/2 8ms 5616 KiB
25 Elfogadva 2/2 8ms 5720 KiB
26 Elfogadva 2/2 8ms 5624 KiB
27 Elfogadva 2/2 8ms 5652 KiB
28 Elfogadva 2/2 8ms 5660 KiB