76442024-01-10 10:31:36CsongiA lehető legkevesebb átszállás (50 pont)cpp17Időlimit túllépés 15/50301ms63040 KiB
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

pair<int, int> elerheto_csucs(int v, vector<vector<int>> allomasok, vector<pair<int, int>> vonat)
{
    int legujabb = 0;
    int index = 0;
    
    for (int i = 0; i < allomasok[v].size(); i++)
    {
        if (vonat[allomasok[v][i]].second > index)
        {
            legujabb = allomasok[v][i];
            index = vonat[allomasok[v][i]].second;
        }
    }
    
    pair<int, int> eredmeny;
    eredmeny.first = legujabb;
    eredmeny.second = index;
    return eredmeny;
}

int main()
{
    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].first = kezdo;
        vonatok[i].second = 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(0);
        
        while (jelenlegi < m)
        {
            pair<int, int> itt = elerheto_csucs(jelenlegi, allomasok, vonatok);
            jelenlegi = itt.second;
            bejaras.push_back(itt.first);
        }
        
        cout << bejaras.size() - 1 << endl;
        
        for (int i = 0; i < bejaras.size(); i++)
        {
            cout << bejaras[i] + 1 << " ";
        }
    }   
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base15/50
1Elfogadva0/03ms1956 KiB
2Időlimit túllépés0/0301ms32624 KiB
3Elfogadva1/13ms2400 KiB
4Időlimit túllépés0/1300ms9960 KiB
5Elfogadva2/23ms2784 KiB
6Elfogadva2/23ms2692 KiB
7Elfogadva2/218ms8368 KiB
8Elfogadva2/217ms10560 KiB
9Elfogadva2/228ms13048 KiB
10Elfogadva2/276ms18900 KiB
11Időlimit túllépés0/2257ms14852 KiB
12Időlimit túllépés0/2272ms17804 KiB
13Elfogadva2/2111ms10984 KiB
14Időlimit túllépés0/2268ms10516 KiB
15Időlimit túllépés0/2268ms13700 KiB
16Időlimit túllépés0/2256ms18228 KiB
17Időlimit túllépés0/2256ms26420 KiB
18Időlimit túllépés0/2280ms28292 KiB
19Időlimit túllépés0/2268ms30816 KiB
20Időlimit túllépés0/2261ms32076 KiB
21Futási hiba0/274ms63040 KiB
22Futási hiba0/272ms63008 KiB
23Futási hiba0/2125ms62980 KiB
24Futási hiba0/2142ms62972 KiB
25Futási hiba0/2167ms62952 KiB
26Futási hiba0/2179ms62944 KiB
27Futási hiba0/2170ms62920 KiB
28Futási hiba0/2174ms62892 KiB