Submission #1144642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144642		mnbvcxz123	Povjerenstvo (COI22_povjerenstvo)	C++20	100 / 100	609 ms	149172 KiB

Main

#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<bool, N> tp_vs;
vec<int> tp;
void tp_dfs(int u) {
    tp_vs[u] = true;
    for (int v : out[u])
        if (!tp_vs[v]) tp_dfs(v);
    tp.push_back(u);
}
int nm_sccs;
arr<int, N> scc;
arr<vec<int>, N> scc_nds;
void scc_dfs(int u) {
    scc[u] = nm_sccs, scc_nds[nm_sccs].push_back(u);
    for (int v : in[u])
        if (!scc[v]) scc_dfs(v);
}
void prcmp() {
    for (int u = 1; u <= n; u++)
        if (!tp_vs[u]) tp_dfs(u);
    reverse(tp.begin(), tp.end());

    for (int u : tp) 
        if (!scc[u]) nm_sccs++, scc_dfs(u);

    // for (int i = 1; i <= nm_sccs; i++) {
    //     cout << i << ": ";
    //     for (int u : scc_nds[i]) cout << u << " ";
    //     cout << endl;
    // }
}

arr<int, N> typ, cnt;
set<pii> ord;
void intl(int id) {
    ord.clear();
    for (int u : scc_nds[id]) {
        if (typ[u] != 0) continue;
        for (int v : out[u])
            cnt[u] += (typ[v] == 0);
        ord.insert({cnt[u], u});
    }
}
void rmv(int u) {
    if (!ord.count({cnt[u], u})) return;
    ord.erase({cnt[u], u});
    for (int v : in[u]) {
        if (!ord.count({cnt[v], v})) continue;
        ord.erase({cnt[v], v});
        cnt[v]--;
        ord.insert({cnt[v], v});
    }
}
arr<int, N> cl;
void cl_dfs(int u) {
    for (int v : out[u]) {
        if (cl[v] || scc[v] != scc[u]) continue;
        cl[v] = (cl[u] == 1) ? 2 : 1;
        cl_dfs(v);
    }
}
void slv(int id) {
    intl(id);
    while (ord.size() && ord.begin()->fir == 0) {
        int u = ord.begin()->sec;
        ord.erase(ord.begin());
        typ[u] = 1, rmv(u);
        for (int v : in[u])
            typ[v] = 2, rmv(v);
    }

    cl[scc_nds[id][0]] = 1, cl_dfs(scc_nds[id][0]);
    for (int u : scc_nds[id]) {
        if (typ[u] != 0) continue;
        if (cl[u] != 1) continue;
        typ[u] = 1;
        for (int v : in[u]) typ[v] = 2;
    }
}

void cmp() {
    for (int i = nm_sccs; i >= 1; i--) 
        slv(i);

    vec<int> ans;
    for (int u = 1; u <= n; u++) {
        assert(typ[u] != 0);
        if (typ[u] == 1) ans.push_back(u);        
    }
    cout << ans.size() << endl;
    for (int u : ans) cout << u << " ";
    cout << endl;
}

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();
}

• Subtask 1: 13 / 13
• Subtask 2: 21 / 21
• Subtask 3: 33 / 33
• Subtask 4: 33 / 33