76582024-01-10 10:54:15CsongiA lehető legkevesebb átszállás (50 pont)cpp17Hibás válasz 20/50181ms62680 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);
            
            if (ujIndex <= jelenlegi) {
                cout << "-1";
                return 0;
            }

            jelenlegi = ujIndex;
            bejaras.push_back(legujabb);
        }
        
        cout << bejaras.size() - 1 << '\n';

        if (bejaras.size() > 1) {
            for (int i = 0; i < bejaras.size() - 1; i++)
            {
                cout << bejaras[i] + 1 << ' ';
            }
        }
    }   
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base20/50
1Hibás válasz0/03ms1828 KiB
2Hibás válasz0/059ms36796 KiB
3Elfogadva1/13ms2416 KiB
4Elfogadva1/13ms2288 KiB
5Részben helyes1/23ms2508 KiB
6Részben helyes1/23ms2608 KiB
7Részben helyes1/27ms6244 KiB
8Részben helyes1/28ms7684 KiB
9Részben helyes1/29ms8712 KiB
10Részben helyes1/214ms11928 KiB
11Részben helyes1/223ms17336 KiB
12Részben helyes1/227ms21188 KiB
13Részben helyes1/29ms7624 KiB
14Részben helyes1/217ms12188 KiB
15Részben helyes1/224ms16364 KiB
16Részben helyes1/229ms21372 KiB
17Részben helyes1/246ms30816 KiB
18Részben helyes1/248ms32596 KiB
19Részben helyes1/250ms35200 KiB
20Részben helyes1/252ms36756 KiB
21Részben helyes1/254ms38552 KiB
22Részben helyes1/254ms38840 KiB
23Futási hiba0/2107ms62680 KiB
24Futási hiba0/2123ms62680 KiB
25Futási hiba0/2150ms62444 KiB
26Futási hiba0/2167ms62416 KiB
27Futási hiba0/2181ms62356 KiB
28Futási hiba0/2151ms62160 KiB