94212024-02-21 14:57:01TuruTamasKritikus munkákcpp17Hibás válasz 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 << " ";
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1828 KiB
2Hibás válasz82ms23116 KiB
subtask20/25
3Elfogadva3ms3988 KiB
4Hibás válasz3ms4364 KiB
5Hibás válasz4ms4872 KiB
6Hibás válasz3ms4744 KiB
7Elfogadva4ms5416 KiB
subtask30/25
8Elfogadva18ms8948 KiB
9Hibás válasz8ms7932 KiB
10Hibás válasz9ms8100 KiB
11Hibás válasz14ms9116 KiB
12Hibás válasz14ms9616 KiB
subtask40/25
13Elfogadva52ms22564 KiB
14Hibás válasz57ms25120 KiB
15Hibás válasz56ms26880 KiB
16Hibás válasz52ms28848 KiB
17Hibás válasz57ms30364 KiB
subtask50/25
18Hibás válasz119ms46700 KiB
19Hibás válasz138ms49592 KiB
20Hibás válasz133ms49592 KiB
21Hibás válasz119ms49852 KiB
22Hibás válasz112ms50676 KiB