76812024-01-10 12:46:21adamA lehető legkevesebb átszállás (50 pont)cpp17Runtime error 34/50192ms64628 KiB
#include <bits/stdc++.h>
using namespace std;

pair<int, int> get_longest (pair<int, int> from, vector<pair<int, int>> trains) {
    pair<int, int> highest;
    for (int i = 0; i < trains.size(); i++) {
        if (trains[i].first - 1 <= from.second && trains[i].second <= trains[i].second)
            if (trains[i].second > highest.second)
                highest = pair(i, trains[i].second - 1);
    }
    return highest;

}

int main() {
    cin.tie(nullptr );
    ios_base::sync_with_stdio(false);
    int train_count = 0;
    int station_count = 0;
    cin >> train_count >> station_count;
    vector<pair<int, int>> trains(train_count, pair(0, 0));
    vector<vector<int>> stations(station_count, vector(0, 0));


    for (int i = 0; i < train_count -1; i++) {
        pair<int, int> train_stops;
        cin >> train_stops.first >> train_stops.second;
        for (int j = 0; j < (train_stops.second - train_stops.first); j++) {
            stations[train_stops.first - 1 + j].push_back(i);
        }

        trains[i] = train_stops;
    }
    int boardings = -1;
    if (stations[station_count-1].empty() == 0) {
        return 0;
    }
    vector<int> boarded_trains(0, 0);
    pair<int, int> current_station (0, 0);
    while (current_station.second != station_count - 1) {
        boardings++;
        current_station = get_longest(current_station, trains);
        boarded_trains.push_back(current_station.first);

    }
    cout << boardings << endl;
    for (int train : boarded_trains) {
        cout << train + 1 << " ";
    }
    cout << endl;



}
SubtaskSumTestVerdictTimeMemory
base34/50
1Accepted0/03ms1864 KiB
2Accepted0/065ms37092 KiB
3Runtime error0/1192ms64628 KiB
4Runtime error0/1170ms64428 KiB
5Accepted2/23ms2668 KiB
6Runtime error0/2192ms63976 KiB
7Accepted2/28ms6580 KiB
8Accepted2/28ms7768 KiB
9Accepted2/29ms9192 KiB
10Accepted2/216ms12248 KiB
11Accepted2/225ms17512 KiB
12Accepted2/228ms21160 KiB
13Accepted2/29ms7556 KiB
14Accepted2/217ms11992 KiB
15Accepted2/224ms16016 KiB
16Accepted2/229ms21304 KiB
17Accepted2/246ms30676 KiB
18Accepted2/252ms32604 KiB
19Accepted2/257ms35220 KiB
20Accepted2/257ms36700 KiB
21Accepted2/264ms38848 KiB
22Accepted2/261ms39072 KiB
23Runtime error0/2103ms62644 KiB
24Runtime error0/2131ms62640 KiB
25Runtime error0/2160ms62616 KiB
26Runtime error0/2136ms62628 KiB
27Runtime error0/2144ms62616 KiB
28Runtime error0/2158ms62604 KiB