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 |