76542024-01-10 10:40:17CsongiA lehető legkevesebb átszállás (50 pont)cpp17Runtime error 37/50165ms64424 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);

    int n, m;
    cin >> n >> m;
    
    vector<pair<int, int>> vonatok(n);
    vector<vector<int>> allomasok(m+1);
    
    bool elso = false, utolso = false;
    
    for (int i = 0; i < n; i++)
    {
        int kezdo, veg;
        cin >> kezdo >> veg;
        vonatok[i] = {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);
            jelenlegi = ujIndex;
            bejaras.push_back(legujabb);
        }
        
        cout << bejaras.size() - 1 << '\n';
        
        for (int i : bejaras)
        {
            cout << i + 1 << ' ';
        }
    }   
}
SubtaskSumTestVerdictTimeMemory
base37/50
1Accepted0/03ms1824 KiB
2Accepted0/059ms36760 KiB
3Accepted1/13ms2232 KiB
4Runtime error0/175ms64424 KiB
5Accepted2/23ms2668 KiB
6Accepted2/22ms2772 KiB
7Accepted2/27ms6376 KiB
8Accepted2/28ms7888 KiB
9Accepted2/29ms9192 KiB
10Accepted2/214ms12272 KiB
11Accepted2/223ms17560 KiB
12Accepted2/228ms21300 KiB
13Accepted2/28ms7752 KiB
14Accepted2/217ms11936 KiB
15Accepted2/223ms16308 KiB
16Accepted2/228ms21392 KiB
17Accepted2/243ms30764 KiB
18Accepted2/245ms32444 KiB
19Accepted2/252ms35268 KiB
20Accepted2/252ms36768 KiB
21Accepted2/254ms38444 KiB
22Accepted2/254ms38836 KiB
23Runtime error0/2109ms62608 KiB
24Runtime error0/2122ms62588 KiB
25Runtime error0/2142ms62568 KiB
26Runtime error0/2165ms62328 KiB
27Runtime error0/2152ms62320 KiB
28Runtime error0/2150ms62312 KiB