61292023-11-02 22:28:16MrChipserA lehető legkevesebb átszállás (50 pont)cpp11Wrong answer 12/5079ms63028 KiB
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n,m;
    cin >> n>>m;
    vector<pair<int,int>>jaratok;
    int ido[m] = {-1};
    int votmaall[m] = {0};
    vector<int> adj[n];
    for(int i = 0; i < n; i++)
    {
        int a,b;
        cin >> a >> b;
        //cout << jaratok.size() << endl;
        for(int j = 0; j < jaratok.size(); j++)
        {
            int elso = jaratok[j].first;
            int utolso = jaratok[j].second;
            //cout << elso << " " << utolso << endl;
            if(a-1 >= elso && a-1 <= utolso)
            {
                adj[j].push_back(i);
                //adj[i].push_back(j);
                //cout  << i<< " " << j << endl;
            }
        }
        //cout << endl;
        jaratok.push_back(make_pair(a-1,b-1));
        //szam.push_back(i+1);
    }
    int votma[n] = {0};
    int elozo[n];
    elozo[0]=-1;
    queue<int>q;
    q.push(0);
    votma[0]=1;
    //int utolso = -1;
    //bool vanu = false;
    while(!q.empty())
    {
        int akt = q.front();
        q.pop();
        for(auto x : adj[akt])
        {
            if(votma[x]==0)
            {
                q.push(x);
                votma[x]=1;
                elozo[x]=akt;
                if(votmaall[jaratok[x].second]==0)
                {
                    votmaall[jaratok[x].second]=1;
                    ido[jaratok[x].second]=x;
                }
                /*if(jaratok[x].second==m-1 && !vanu)
                {
                    //cout << x << " "
                    vanu = true;
                    utolso = x;
                }*/
                //cout << akt << " " << x << endl;
            }
        }

    }
    if(ido[m-1]==-1)
    {
        cout << -1;
        return 0;
    }
    //cout << utolso << endl;
    int uthossz = 0;
    vector<int>ut;
    int x = ido[m-1];
    while(x!=-1)
    {
        ut.insert(ut.begin(),x);
        x = elozo[x];
        uthossz++;
    }
    cout << uthossz-1 << endl;
    sort(ut.begin(),ut.end());
    for(int i = 0; i < ut.size(); i++)
        cout << ut[i]+1 << " ";
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base12/50
1Accepted0/03ms1808 KiB
2Accepted0/064ms7700 KiB
3Wrong answer0/13ms2232 KiB
4Wrong answer0/13ms2440 KiB
5Wrong answer0/23ms2684 KiB
6Accepted2/23ms2872 KiB
7Accepted2/24ms3680 KiB
8Accepted2/26ms4164 KiB
9Wrong answer0/27ms4652 KiB
10Wrong answer0/212ms5556 KiB
11Wrong answer0/214ms5760 KiB
12Wrong answer0/221ms6748 KiB
13Wrong answer0/24ms4644 KiB
14Accepted2/27ms5204 KiB
15Wrong answer0/29ms5740 KiB
16Accepted2/220ms6972 KiB
17Wrong answer0/235ms8036 KiB
18Wrong answer0/243ms8668 KiB
19Wrong answer0/250ms9084 KiB
20Wrong answer0/254ms9212 KiB
21Wrong answer0/264ms9964 KiB
22Accepted2/264ms10104 KiB
23Runtime error0/279ms63028 KiB
24Runtime error0/271ms63016 KiB
25Runtime error0/278ms62988 KiB
26Runtime error0/270ms62748 KiB
27Runtime error0/276ms62520 KiB
28Runtime error0/276ms62528 KiB