76482024-01-10 10:33:42CsongiA lehető legkevesebb átszállás (50 pont)cpp17Futási hiba 37/50199ms64444 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>>& 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 << ' ';
        }
    }   
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base37/50
1Elfogadva0/03ms1996 KiB
2Elfogadva0/054ms36968 KiB
3Elfogadva1/13ms2348 KiB
4Futási hiba0/187ms64444 KiB
5Elfogadva2/23ms2660 KiB
6Elfogadva2/23ms2720 KiB
7Elfogadva2/27ms6352 KiB
8Elfogadva2/28ms7472 KiB
9Elfogadva2/29ms8832 KiB
10Elfogadva2/214ms11864 KiB
11Elfogadva2/225ms17004 KiB
12Elfogadva2/227ms20920 KiB
13Elfogadva2/29ms7516 KiB
14Elfogadva2/217ms11760 KiB
15Elfogadva2/224ms15792 KiB
16Elfogadva2/230ms20880 KiB
17Elfogadva2/243ms30204 KiB
18Elfogadva2/246ms32000 KiB
19Elfogadva2/252ms34464 KiB
20Elfogadva2/256ms36156 KiB
21Elfogadva2/257ms37840 KiB
22Elfogadva2/257ms38144 KiB
23Futási hiba0/2120ms63300 KiB
24Futási hiba0/2144ms63292 KiB
25Futási hiba0/2164ms63264 KiB
26Futási hiba0/2148ms63028 KiB
27Futási hiba0/2199ms62792 KiB
28Futási hiba0/2152ms62772 KiB