116182024-10-31 19:28:48csdavidKerékpártúra (50 pont)cpp17Runtime error 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;
}
SubtaskSumTestVerdictTimeMemory
base29/50
1Accepted0/01ms332 KiB
2Runtime error0/0344ms32000 KiB
3Runtime error0/2326ms32000 KiB
4Accepted2/21ms320 KiB
5Accepted2/21ms320 KiB
6Accepted2/21ms320 KiB
7Runtime error0/2203ms32000 KiB
8Runtime error0/2186ms32000 KiB
9Runtime error0/2317ms32000 KiB
10Accepted2/23ms320 KiB
11Accepted2/24ms404 KiB
12Accepted2/210ms568 KiB
13Runtime error0/2257ms32000 KiB
14Time limit exceeded0/2442ms32000 KiB
15Accepted3/332ms1852 KiB
16Accepted4/437ms2104 KiB
17Accepted4/454ms2616 KiB
18Accepted3/348ms2368 KiB
19Accepted3/343ms2448 KiB
20Time limit exceeded0/3500ms22840 KiB
21Time limit exceeded0/3483ms15304 KiB
22Time limit exceeded0/3500ms14624 KiB