7530 2024. 01. 09 13:30:08 gyjazmin A lehető legkevesebb átszállás (50 pont) cpp17 Elfogadva 50/50 10ms 5536 KiB


#include <iostream>
#include <vector>
using namespace std;
vector<int> v(1);
vector<vector<int>> graf;
int cv = 0;
bool kovetk() {
    v.push_back(0);
    int eleje= cv;
    int s = v.size()-1;
    int i = v[s-1]+1;
    int maxv=cv;
    while (i <= graf.size() - 1&& graf[i][0] <= cv) {
        if (graf[i][1] > maxv) {
            maxv = graf[i][1];
            v[s] = i;
        }        
        i++;
    }
    cv = maxv;
    if (eleje == cv) {
        return false;
    }
    else {
        return true;
    }

}
int main()
{
    int n,m;
    cin >> n>>m;
    graf.resize(n+1);    
    for (int i = 0;i < n;i++) {
        int egyik, masik;
        cin >> egyik >> masik;
        graf[i].resize(2);
        graf[i + 1].push_back(egyik);
        graf[i + 1].push_back(masik);
        if (egyik == 1&& masik >cv) {
            cv = masik;
            v[0] = i + 1;
        }
    }
    if (cv == 0) {
        cout << -1 << endl;
    }
    else {
        bool eljut=true;
        while (cv != m) {
            eljut = kovetk();
            if (!eljut) {
                cout << -1 << endl;
                break;
            }
        }
        if (eljut) {
            cout << v.size() - 1 << endl;
            for (int i = 0;i < v.size();i++) {
                cout << v[i] << " ";
            }
            cout << endl;
        }
    }

    
}

Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1872 KiB
2 Elfogadva 0/0 10ms 3024 KiB
3 Elfogadva 1/1 3ms 2288 KiB
4 Elfogadva 1/1 3ms 2496 KiB
5 Elfogadva 2/2 3ms 2572 KiB
6 Elfogadva 2/2 3ms 2720 KiB
7 Elfogadva 2/2 3ms 3120 KiB
8 Elfogadva 2/2 4ms 3360 KiB
9 Elfogadva 2/2 4ms 3488 KiB
10 Elfogadva 2/2 4ms 3620 KiB
11 Elfogadva 2/2 6ms 3936 KiB
12 Elfogadva 2/2 7ms 4072 KiB
13 Elfogadva 2/2 3ms 3956 KiB
14 Elfogadva 2/2 4ms 4220 KiB
15 Elfogadva 2/2 4ms 4356 KiB
16 Elfogadva 2/2 7ms 4492 KiB
17 Elfogadva 2/2 8ms 4896 KiB
18 Elfogadva 2/2 8ms 4984 KiB
19 Elfogadva 2/2 9ms 4980 KiB
20 Elfogadva 2/2 9ms 5008 KiB
21 Elfogadva 2/2 10ms 5204 KiB
22 Elfogadva 2/2 10ms 5180 KiB
23 Elfogadva 2/2 9ms 5184 KiB
24 Elfogadva 2/2 9ms 5324 KiB
25 Elfogadva 2/2 9ms 5284 KiB
26 Elfogadva 2/2 9ms 5344 KiB
27 Elfogadva 2/2 10ms 5536 KiB
28 Elfogadva 2/2 10ms 5496 KiB