9421 2024. 02. 21 14:57:01 TuruTamas Kritikus munkák cpp17 Hibás válasz 0/100 138ms 50676 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 << " ";
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1828 KiB
2 Hibás válasz 82ms 23116 KiB
subtask2 0/25
3 Elfogadva 3ms 3988 KiB
4 Hibás válasz 3ms 4364 KiB
5 Hibás válasz 4ms 4872 KiB
6 Hibás válasz 3ms 4744 KiB
7 Elfogadva 4ms 5416 KiB
subtask3 0/25
8 Elfogadva 18ms 8948 KiB
9 Hibás válasz 8ms 7932 KiB
10 Hibás válasz 9ms 8100 KiB
11 Hibás válasz 14ms 9116 KiB
12 Hibás válasz 14ms 9616 KiB
subtask4 0/25
13 Elfogadva 52ms 22564 KiB
14 Hibás válasz 57ms 25120 KiB
15 Hibás válasz 56ms 26880 KiB
16 Hibás válasz 52ms 28848 KiB
17 Hibás válasz 57ms 30364 KiB
subtask5 0/25
18 Hibás válasz 119ms 46700 KiB
19 Hibás válasz 138ms 49592 KiB
20 Hibás válasz 133ms 49592 KiB
21 Hibás válasz 119ms 49852 KiB
22 Hibás válasz 112ms 50676 KiB