94212024-02-21 14:57:01TuruTamasKritikus munkákcpp17Wrong answer 0/100138ms50676 KiB
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
ifstream in_file("C:\\verseny\\minta\\be1.txt");
#define input in_file
#define INTHENAMEOFGOD
#else
#define input cin
#define INTHENAMEOFGOD \
    ios::sync_with_stdio(0); \
    cin.tie(0); \
    cout.tie(0);
#endif
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<ll, ll> pii;

ll N, M, a, b;
vvi G, Gi;
vb vis;
vi oda, vissza;
vi *vr;

ll dfs(ll x) {
    ll ret = 1;
    vis[x] = true;
    for (ll next : G[x]) {
        if (!vis[next]) {
            ret += dfs(next);
        } else {
            (*vr)[x] += (*vr)[next];
        }
    }
    (*vr)[x] += ret;
    return ret;
}

int main() {
    INTHENAMEOFGOD
    input >> N >> M;
    G.resize(N + 2);
    Gi.resize(N + 2);
    for (ll n = 0; n < M; n++) {
        input >> a >> b;
        a--; b--;
        G[a].push_back(b);
        Gi[b].push_back(a);
    }

    for (ll n = 0; n < N; n++) {
        if (Gi[n].size() == 0) {
            G[N].push_back(n);
            Gi[n].push_back(N);
        }
    }
    for (ll n = 0; n < N; n++) {
        if (G[n].size() == 0) {
            Gi[N+1].push_back(n);
            G[n].push_back(N+1);
        }
    }

    oda.assign(N + 2, 0);
    vr = &oda;
    vis.assign(N + 2, false);
    dfs(N);


    swap(G, Gi);
    vissza.assign(N + 2, 0);
    vr = &vissza;
    vis.assign(N + 2, false);
    dfs(N + 1);

    vi ans;
    for (ll n = 0; n < N + 2; n++) {
        if (oda[n] + vissza[n] == N + 3) {
            ans.push_back(n);
        }
    }
    cout << ans.size() - 2 << "\n";
    for (ll i : ans) {
        if (i < N)
            cout << i + 1 << " ";
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1828 KiB
2Wrong answer82ms23116 KiB
subtask20/25
3Accepted3ms3988 KiB
4Wrong answer3ms4364 KiB
5Wrong answer4ms4872 KiB
6Wrong answer3ms4744 KiB
7Accepted4ms5416 KiB
subtask30/25
8Accepted18ms8948 KiB
9Wrong answer8ms7932 KiB
10Wrong answer9ms8100 KiB
11Wrong answer14ms9116 KiB
12Wrong answer14ms9616 KiB
subtask40/25
13Accepted52ms22564 KiB
14Wrong answer57ms25120 KiB
15Wrong answer56ms26880 KiB
16Wrong answer52ms28848 KiB
17Wrong answer57ms30364 KiB
subtask50/25
18Wrong answer119ms46700 KiB
19Wrong answer138ms49592 KiB
20Wrong answer133ms49592 KiB
21Wrong answer119ms49852 KiB
22Wrong answer112ms50676 KiB