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

using namespace std;

pair<int, int> elerhetolncsucs(int v, vector<vector<int>> allomasok, vector<pair<int, int>> vonat)
{
    int legn = 0;
    int ind = 0;
    for (int i = 0; i < allomasok[v].size(); i++)
    {
        if (vonat[allomasok[v][i]].second > ind)
        {
            legn = allomasok[v][i];
            ind = vonat[allomasok[v][i]].second;
        }
    }
    pair<int, int> ki;
    ki.first = legn;
    ki.second = ind;
    return ki;
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> vonat(n);
    vector<vector<int>> allomasok(m+1);
    bool egyes = false, utolso = false;
    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        vonat[i].first = a;
        vonat[i].second = b;
        if (a == 1)
            egyes = true;
        if (b == m)
            utolso = true;
        for (int j = a; j <= b; j++)
        {
            allomasok[j].push_back(i);
        }
    }
    if (!egyes || !utolso)
    {
        cout << "-1";
    }
    else
    {
        int most = 1;
        vector<int> bejaras(0);
        while (most < m)
        {
            pair<int, int> itt = elerhetolncsucs(most, allomasok, vonat);
            most = 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/03ms1808 KiB
2Időlimit túllépés0/0301ms32580 KiB
3Elfogadva1/13ms2328 KiB
4Időlimit túllépés0/1300ms10132 KiB
5Elfogadva2/23ms2640 KiB
6Elfogadva2/23ms2848 KiB
7Elfogadva2/218ms8844 KiB
8Elfogadva2/217ms11120 KiB
9Elfogadva2/227ms13496 KiB
10Elfogadva2/276ms19108 KiB
11Időlimit túllépés0/2256ms15124 KiB
12Időlimit túllépés0/2259ms18140 KiB
13Elfogadva2/2108ms11336 KiB
14Időlimit túllépés0/2266ms10736 KiB
15Időlimit túllépés0/2263ms14356 KiB
16Időlimit túllépés0/2254ms19088 KiB
17Időlimit túllépés0/2261ms27072 KiB
18Időlimit túllépés0/2270ms28708 KiB
19Időlimit túllépés0/2246ms31004 KiB
20Időlimit túllépés0/2263ms32200 KiB
21Futási hiba0/271ms62832 KiB
22Futási hiba0/271ms62804 KiB
23Futási hiba0/2108ms62576 KiB
24Futási hiba0/2123ms62556 KiB
25Futási hiba0/2137ms62548 KiB
26Futási hiba0/2145ms62544 KiB
27Futási hiba0/2155ms62500 KiB
28Futási hiba0/2155ms62512 KiB