178522025-09-19 18:54:41KristófA lehető legkevesebb átszállás (50 pont)cpp17Elfogadva 50/508ms508 KiB
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<pair<int,int>> utak(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> utak[i].first >> utak[i].second;
    }

    int tovabbm = 1;        // meddig jutottunk biztosan
    int tovabbmtmp = 1;     // ideiglenes legjobb kiterjesztés
    int indextmp = -1;      // legjobb vonat indexe
    vector<int> megoldas;

    int i = 1;
    while (tovabbm < m) {
        bool talalt = false;

        // Keressük a legjobb vonatot, ami indul a jelenlegi szakaszról
        while (i <= n && utak[i].first <= tovabbm) {
            if (utak[i].second > tovabbmtmp) {
                tovabbmtmp = utak[i].second;
                indextmp = i;
                talalt = true;
            }
            i++;
        }

        if (!talalt) { // nincs további vonat
            cout << -1 << "\n";
            return 0;
        }

        // Hozzáadjuk a kiválasztott vonatot
        megoldas.push_back(indextmp);
        tovabbm = tovabbmtmp;
    }

    // Átszállások száma = kiválasztott vonatok - 1
    cout << (int)megoldas.size() - 1 << "\n";
    for (int idx : megoldas) cout << idx << " ";
    cout << "\n";

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/08ms316 KiB
3Elfogadva1/11ms316 KiB
4Elfogadva1/11ms316 KiB
5Elfogadva2/21ms316 KiB
6Elfogadva2/21ms508 KiB
7Elfogadva2/21ms408 KiB
8Elfogadva2/22ms316 KiB
9Elfogadva2/22ms316 KiB
10Elfogadva2/23ms316 KiB
11Elfogadva2/23ms316 KiB
12Elfogadva2/24ms316 KiB
13Elfogadva2/22ms316 KiB
14Elfogadva2/22ms316 KiB
15Elfogadva2/23ms508 KiB
16Elfogadva2/24ms316 KiB
17Elfogadva2/26ms388 KiB
18Elfogadva2/26ms316 KiB
19Elfogadva2/27ms472 KiB
20Elfogadva2/27ms368 KiB
21Elfogadva2/28ms480 KiB
22Elfogadva2/28ms472 KiB
23Elfogadva2/27ms316 KiB
24Elfogadva2/27ms316 KiB
25Elfogadva2/27ms316 KiB
26Elfogadva2/27ms472 KiB
27Elfogadva2/27ms500 KiB
28Elfogadva2/27ms316 KiB