129762025-01-04 12:55:30CsongiA lehető legkevesebb átszállás (50 pont)cpp17Runtime error 38/50165ms32000 KiB
#include <iostream>
#include <vector>
#define ll long long
using namespace std;

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

    for (ll 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);

    ll n, m;
    cin >> n >> m;

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

    bool elso = false, utolso = false;

    for (ll i = 0; i < n; i++)
    {
        ll kezdo, veg;
        cin >> kezdo >> veg;
        if (i != 0 && vonatok[i-1].first == kezdo && vonatok[i-1].second > veg)
        {

        }
        else
        {
            vonatok[i] = { kezdo, veg };

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

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

    if (!elso || !utolso)
    {
        cout << "-1";
    }
    else
    {
        ll jelenlegi = 1;
        vector<ll> 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 (ll i : bejaras)
        {
            cout << i + 1 << ' ';
        }
    }
}
SubtaskSumTestVerdictTimeMemory
base38/50
1Accepted0/01ms500 KiB
2Accepted0/071ms31032 KiB
3Accepted1/11ms320 KiB
4Accepted1/11ms320 KiB
5Accepted2/21ms560 KiB
6Accepted2/21ms320 KiB
7Accepted2/27ms3468 KiB
8Accepted2/28ms4408 KiB
9Accepted2/212ms5664 KiB
10Accepted2/218ms8544 KiB
11Accepted2/232ms12600 KiB
12Accepted2/235ms15928 KiB
13Accepted2/210ms3640 KiB
14Accepted2/219ms7272 KiB
15Accepted2/229ms10764 KiB
16Accepted2/241ms15672 KiB
17Accepted2/263ms23604 KiB
18Accepted2/261ms25388 KiB
19Accepted2/272ms27620 KiB
20Accepted2/268ms28908 KiB
21Accepted2/279ms30484 KiB
22Accepted2/276ms30736 KiB
23Runtime error0/2101ms32000 KiB
24Runtime error0/294ms32000 KiB
25Runtime error0/2148ms32000 KiB
26Runtime error0/2111ms32000 KiB
27Runtime error0/2165ms32000 KiB
28Runtime error0/2163ms32000 KiB