82782024-01-14 08:58:28MagyarKendeSZLGKerékpártúra (50 pont)cpp17Time limit exceeded 24/50500ms4336 KiB
#include <bits/stdc++.h>
#define speed cin.tie(0); ios::sync_with_stdio(0)
using namespace std;

vector<vector<int>> g;
int N, M, K;
vector<bool> cache;

bool goback(int s) {
    if (cache[s]) return 1;

    vector<bool> vis(N + 1);
    vector<int> from(N + 1);
    queue<int> q;
    vis[s] = 1;
    q.push(s);

    while (!q.empty()) {
        int node = q.front(); q.pop();

        if (cache[node]) {
            return 1;
        }

        if (node == K) {
            int curr = node;
            do {
                cache[curr] = 1;
                curr = from[curr];
            } while (curr);

            return 1;
        }

        for (int neigh : g[node]) {
            if (!vis[neigh]) {
                vis[neigh] = 1;
                from[neigh] = node;
                q.push(neigh);
            }
        }
    }

    return 0;
}

int main()
{
    speed;

    cin >> N >> M >> K;

    g.resize(N + 1);
    while (M--) {
        int U, V;
        cin >> U >> V;
        g[U].push_back(V);
    }

    vector<bool> vis(N + 1);
    queue<int> q;
    q.push(K);
    vis[K] = 1;
    while (!q.empty()) {
        int node = q.front(); q.pop();
        for (int neigh : g[node]) {
            if (!vis[neigh]) {
                vis[neigh] = 1; 
                q.push(neigh);
            }
        }
    }

    vector<int> base;

    cache.resize(N + 1);

    for (int i = 1; i <= N; i++) {
        if (i != K && vis[i] && goback(i)) {
            base.push_back(i);
        }
    }

    unordered_set<int> result;
    for (int x : base) {
        result.insert(x);
        for (int neigh : g[x]) {
            if (neigh != K) result.insert(neigh);
        }
    }

    for (int neigh : g[K]) {
        result.insert(neigh);
    }

    if (result.empty()) {
        cout << 0;
        exit(0);
    }

    cout << result.size() << '\n';

    for (int x : result) cout << x << ' ';
    cout << '\n';
}
SubtaskSumTestVerdictTimeMemory
base24/50
1Accepted0/03ms1828 KiB
2Time limit exceeded0/0500ms1864 KiB
3Accepted2/23ms2128 KiB
4Accepted2/23ms2332 KiB
5Accepted2/22ms2420 KiB
6Accepted2/23ms2424 KiB
7Accepted2/23ms2644 KiB
8Accepted2/24ms2924 KiB
9Accepted2/23ms3136 KiB
10Accepted2/24ms3252 KiB
11Accepted2/246ms3144 KiB
12Accepted2/237ms3348 KiB
13Accepted2/270ms3600 KiB
14Accepted2/2123ms3804 KiB
15Time limit exceeded0/3470ms3288 KiB
16Time limit exceeded0/4472ms3180 KiB
17Time limit exceeded0/4474ms3456 KiB
18Time limit exceeded0/3442ms3348 KiB
19Time limit exceeded0/3477ms3324 KiB
20Time limit exceeded0/3465ms3928 KiB
21Time limit exceeded0/3437ms4120 KiB
22Time limit exceeded0/3442ms4336 KiB