116192024-10-31 19:30:13csdavidKerékpártúra (50 pont)cpp17Futási hiba 29/50500ms32000 KiB
#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;

struct david{
    vector<int> v;
};

int main()
{
    int n, m, k, x, y;
    cin >> n >> m >> k;
    queue<int> q;
    david a[n+1], b[n+1];
    int bejart[n+1], jo[n+1], ok[n+1];
    for(auto& it: bejart){
        it=0;
    }
    for(auto& it:jo){
        it=0;
    }
    for(auto& it:ok){
        it=0;
    }
    bejart[k]=1;
    for(int i=0; i<m; i++){
        cin >> x >> y;
        a[x].v.push_back(y);
        b[y].v.push_back(x);
    }
    q.push(k);
    /*cout << "\n\n";
    for(int i=1; i<=n; i++){
        for(int j=0; j<b[i].size(); j++){
            cout << i << ' ' << b[i][j] << '\n';
        }
    }*/
    while(!q.empty()){
        /*cout << 'x';
        cout << b[q.front()].v.size();*/
        for(int i=0; i<b[q.front()].v.size(); i++){

            if(bejart[b[q.front()].v[i]]==0){
                q.push(b[q.front()].v[i]);
                x=b[q.front()].v[i];
                bejart[b[q.front()].v[i]]=1;
                jo[b[q.front()].v[i]]=1;
            }
        }
        q.pop();
    }
    q.push(k);
    for(auto& it: bejart){
        it=0;
    }
    bejart[k]=1;
    jo[k]=1;
    set<int> solution;
    /*for(int i=1; i<=n; i++){
        if(jo[i]){
            cout << i << ' ';
        }
    }*/
    //cout << endl;

    while(!q.empty()){
        x=q.front();

        //cout << x << ' ';

        for(int i=0; i<a[x].v.size(); i++){
            if(bejart[a[x].v[i]]==0){
                //cout << a[x].v[i] << '\n';
                bejart[a[x].v[i]]==1;
                solution.insert(a[x].v[i]);
                ok[a[x].v[i]]==1;
                if(jo[a[x].v[i]]) q.push(a[x].v[i]);
            }
        }
        q.pop();
    }





    ok[k]=0;
    int megoldas=0;
    for(int i=1; i<=n; i++){
        if(ok[i]==1){
            megoldas++;
        }
    }

    cout << solution.size() << '\n';
    for(auto& it:solution){
        cout << it <<  ' ';
    }




    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base29/50
1Elfogadva0/02ms320 KiB
2Futási hiba0/0342ms32000 KiB
3Futási hiba0/2326ms32000 KiB
4Elfogadva2/21ms508 KiB
5Elfogadva2/21ms320 KiB
6Elfogadva2/21ms320 KiB
7Futási hiba0/2199ms32000 KiB
8Futási hiba0/2187ms32000 KiB
9Futási hiba0/2312ms32000 KiB
10Elfogadva2/23ms320 KiB
11Elfogadva2/24ms568 KiB
12Elfogadva2/210ms548 KiB
13Futási hiba0/2257ms32000 KiB
14Időlimit túllépés0/2451ms32000 KiB
15Elfogadva3/334ms1848 KiB
16Elfogadva4/437ms2104 KiB
17Elfogadva4/454ms2616 KiB
18Elfogadva3/350ms2360 KiB
19Elfogadva3/343ms2360 KiB
20Időlimit túllépés0/3500ms23020 KiB
21Időlimit túllépés0/3479ms15068 KiB
22Időlimit túllépés0/3500ms14792 KiB