Submission #1129008

#TimeUsernameProblemLanguageResultExecution timeMemory
1129008gygPovjerenstvo (COI22_povjerenstvo)C++20
34 / 100
1099 ms115680 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define arr array #define vec vector #define pii pair<int, int> #define fir first #define sec second const int N = 5e5 + 5; int n, m; arr<vec<int>, N> in, out; arr<int, N> cnt; arr<bool, N> dlt; set<pii> ord; void rmv(int u) { ord.erase({cnt[u], u}); dlt[u] = true; for (int v : in[u]) { if (dlt[v]) continue; ord.erase({cnt[v], v}); cnt[v]--; ord.insert({cnt[v], v}); } } arr<int, N> cl; void dfs(int u) { for (int v : in[u]) { if (cl[v]) continue; cl[v] = (cl[u] == 1) ? 2 : 1, dfs(v); } for (int v : out[u]) { if (cl[v]) continue; cl[v] = (cl[u] == 1) ? 2 : 1, dfs(v); } } void prcmp() { for (int u = 1; u <= n; u++) cnt[u] = out[u].size(), ord.insert({cnt[u], u}); for (int u = 1; u <= n; u++) if (!cl[u]) cl[u] = 1, dfs(u); } vec<int> ans; void cmp() { while (ord.size() && ord.begin()->fir == 0) { int u = ord.begin()->sec; ord.erase(ord.begin()); ans.push_back(u); rmv(u); for (int v : in[u]) if (!dlt[v]) rmv(v); } for (int u = 1; u <= n; u++) if (cl[u] == 1 && !dlt[u]) ans.push_back(u); } signed main() { // freopen("a.in", "r", stdin); cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; out[u].push_back(v), in[v].push_back(u); } prcmp(); cmp(); cout << ans.size() << '\n'; for (int u : ans) cout << u << " "; cout << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...