7744 2024. 01. 10 21:53:52 Csongi A lehető legkevesebb átszállás (50 pont) cpp17 Hibás válasz 6/50 189ms 63416 KiB
#include <iostream>
#include <vector>

using namespace std;

pair<int, int> elerheto_csucs(int v, const vector<vector<int>>& allomasok, const vector<pair<int, int>>& vonatok)
{
    int legujabb = 0, index = 0;

    for (int i : allomasok[v])
    {
        if (vonatok[i].second > index)
        {
            legujabb = i;
            index = vonatok[i].second;
        }
    }

    return { legujabb, index };
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> vonatok;
    vector<vector<int>> allomasok(m + 1);

    bool elso = false, utolso = false;

    int prev_veg = -1;

    for (int i = 0; i < n; i++)
    {
        int kezdo, veg;
        cin >> kezdo >> veg;
        if (i != 0 && vonatok.back().first == kezdo && vonatok.back().second > veg)
        {

        }
        else
        {
            vonatok.push_back({ kezdo, veg });

            if (kezdo == 1)
                elso = true;
            if (veg == m)
                utolso = true;

            for (int j = kezdo; j <= veg; j++)
            {
                allomasok[j].push_back(i);
            }
        }
        
    }

    if (!elso || !utolso)
    {
        cout << "-1";
    }
    else
    {
        int jelenlegi = 1;
        vector<int> bejaras;

        while (jelenlegi < m)
        {
            auto [legujabb, ujIndex] = elerheto_csucs(jelenlegi, allomasok, vonatok);
            if (ujIndex <= jelenlegi) {
                cout << "-1";  // vegtelen loop?
                return 0;
            }
            jelenlegi = ujIndex;
            bejaras.push_back(legujabb);
        }

        cout << bejaras.size() - 1 << '\n';

        for (int i : bejaras)
        {
            cout << i + 1 << ' ';
        }
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 6/50
1 Elfogadva 0/0 3ms 1824 KiB
2 Hibás válasz 0/0 57ms 36268 KiB
3 Elfogadva 1/1 3ms 2316 KiB
4 Elfogadva 1/1 3ms 2392 KiB
5 Elfogadva 2/2 3ms 2448 KiB
6 Elfogadva 2/2 3ms 2516 KiB
7 Hibás válasz 0/2 7ms 5952 KiB
8 Hibás válasz 0/2 8ms 7044 KiB
9 Hibás válasz 0/2 9ms 8300 KiB
10 Hibás válasz 0/2 14ms 11700 KiB
11 Hibás válasz 0/2 24ms 16464 KiB
12 Hibás válasz 0/2 28ms 20020 KiB
13 Hibás válasz 0/2 9ms 7136 KiB
14 Hibás válasz 0/2 17ms 11528 KiB
15 Hibás válasz 0/2 23ms 15628 KiB
16 Hibás válasz 0/2 30ms 20420 KiB
17 Hibás válasz 0/2 46ms 29616 KiB
18 Hibás válasz 0/2 48ms 31648 KiB
19 Hibás válasz 0/2 52ms 33988 KiB
20 Hibás válasz 0/2 54ms 35416 KiB
21 Hibás válasz 0/2 57ms 37104 KiB
22 Hibás válasz 0/2 57ms 37500 KiB
23 Futási hiba 0/2 123ms 63416 KiB
24 Futási hiba 0/2 145ms 63404 KiB
25 Futási hiba 0/2 165ms 63388 KiB
26 Futási hiba 0/2 175ms 63356 KiB
27 Futási hiba 0/2 187ms 63332 KiB
28 Futási hiba 0/2 189ms 63312 KiB