Submission #963958

#	Time	Username	Problem	Language	Result	Execution time	Memory
963958		becaido	Povjerenstvo (COI22_povjerenstvo)	C++17	100 / 100	569 ms	152008 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 5e5 + 5;

int n, m;
int ans, cl[SIZE];
vector<int> adj[SIZE], rev[SIZE];

int tid, sid, dfn[SIZE], low[SIZE], ist[SIZE], scc[SIZE];
vector<int> st, v[SIZE];

void dfs(int pos) {
    dfn[pos] = low[pos] = ++tid;
    st.pb(pos), ist[pos] = 1;
    for (int np : adj[pos]) {
        if (dfn[np] == 0) {
            dfs(np);
            low[pos] = min(low[pos], low[np]);
        } else if (ist[np]) {
            low[pos] = min(low[pos], dfn[np]);
        }
    }
    if (dfn[pos] == low[pos]) {
        sid++;
        while (st.size()) {
            int x = st.back();
            st.pop_back();
            ist[x] = 0;
            scc[x] = sid;
            v[sid].pb(x);
            if (x == pos) break;
        }
    }
}

void solve() {
    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        adj[a].pb(b);
        rev[b].pb(a);
    }
    FOR (i, 1, n) if (dfn[i] == 0) dfs(i);
    FOR (i, 1, sid) {
        for (int x : v[i]) {
            for (int y : adj[x]) if (cl[y] == 2) {
                cl[x] = 1;
                break;
            }
        }
        for (int x : v[i]) if (cl[x] == 0) {
            vector<int> u;
            queue<int> q;
            cl[x] = -1, q.push(x);
            while (q.size()) {
                int pos = q.front();
                q.pop();
                u.pb(pos);
                for (int np : adj[pos]) if (scc[np] == i && cl[np] == 0) {
                    cl[np] = -1;
                    q.push(np);
                }
                for (int np : rev[pos]) if (scc[np] == i && cl[np] == 0) {
                    cl[np] = -1;
                    q.push(np);
                }
            }
            int s = 0;
            for (int y : u) {
                bool f = 1;
                for (int z : adj[y]) if (cl[z] != 1) {
                    f = 0;
                    break;
                }
                if (f) {
                    s = y;
                    break;
                }
            }
            if (s == 0) s = x;
            cl[s] = 2, q.push(s);
            while (q.size()) {
                int pos = q.front();
                q.pop();
                for (int np : adj[pos]) if (cl[np] == -1) {
                    cl[np] = 3 - cl[pos];
                    q.push(np);
                }
                for (int np : rev[pos]) if (cl[np] == -1) {
                    cl[np] = 3 - cl[pos];
                    q.push(np);
                }
            }
        }
    }
    FOR (i, 1, n) ans += (cl[i] == 2);
    cout << ans << '\n';
    FOR (i, 1, n) if (cl[i] == 2) cout << i << ' ';
    cout << '\n';
}

int main() {
    Waimai;
    solve();
}

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