76392024-01-10 10:19:21CsongiA lehető legkevesebb átszállás (50 pont)cpp14Time limit exceeded 15/50301ms63864 KiB
#include <iostream>
#include <bits/stdc++.h>
#include <vector>

using namespace std;

pair<int, int> elerhetolncsucs(int v, vector<vector<int>> allomasok, vector<pair<int, int>> vonat)
{
    int legn = 0;
    int ind = 0;
    vector<int> temp(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; //villamos 0-n
    ki.second = ind; //csucs 1-m
    return ki;
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> vonatok(n);
    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;
        vonatok[i] = b - a + 1; //merete a vonatnak
        vonat[i].first = a;
        vonat[i].second = b;
        if (a == 1)
            egyes = true;
        if (b == m)
            utolso = true;
        //cout << a << " " << b << endl;
        for (int j = a; j <= b; j++)
        {
            allomasok[j].push_back(i);
        }
    }
    if (!egyes || !utolso)
    {
        cout << "-1";
        exit(0);
    }
    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 << most << " " << itt.first;
    }
    cout << bejaras.size() - 1 << endl;
    for (int i = 0; i < bejaras.size(); i++)
    {
        cout << bejaras[i] + 1 << " ";
    }
}
SubtaskSumTestVerdictTimeMemory
base15/50
1Accepted0/03ms1812 KiB
2Time limit exceeded0/0301ms32460 KiB
3Accepted1/13ms1976 KiB
4Time limit exceeded0/1275ms9536 KiB
5Accepted2/23ms2112 KiB
6Accepted2/23ms2200 KiB
7Accepted2/217ms7824 KiB
8Accepted2/217ms10428 KiB
9Accepted2/227ms12696 KiB
10Accepted2/272ms18508 KiB
11Time limit exceeded0/2272ms14120 KiB
12Time limit exceeded0/2270ms17224 KiB
13Accepted2/2111ms10328 KiB
14Time limit exceeded0/2279ms9708 KiB
15Time limit exceeded0/2266ms13000 KiB
16Time limit exceeded0/2257ms17868 KiB
17Time limit exceeded0/2261ms25836 KiB
18Time limit exceeded0/2259ms27644 KiB
19Time limit exceeded0/2246ms29944 KiB
20Time limit exceeded0/2270ms31248 KiB
21Runtime error0/271ms63864 KiB
22Runtime error0/271ms63840 KiB
23Runtime error0/2108ms63604 KiB
24Runtime error0/2122ms63572 KiB
25Runtime error0/2135ms63556 KiB
26Runtime error0/2144ms63544 KiB
27Runtime error0/2152ms63544 KiB
28Runtime error0/2151ms63524 KiB