Submission #1209421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209421		Fatonim	Povjerenstvo (COI22_povjerenstvo)	C++20	100 / 100	468 ms	149872 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#ifdef ONPC
#include "debug.h"
#else
#define dbg(...)
#endif

#define ll long long
#define int long long
#define ld long double
#define pi pair<int, int>
#define sz(a) ((int)(a.size()))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sqr(n) ((n) * (n))
#define divup(a, b) (((a) + (b)-1) / (b))
#define popcount(n) __builtin_popcountll(n)
#define clz(n) __builtin_clzll(n)
#define Fixed(a) cout << fixed << setprecision(12) << a;

template <class T> bool chmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool chmax(T& a, const T& b) { return b > a ? a = b, 1 : 0; }

const int mod = 998244353; // 998244353 1e9 + 7
const ll inf = (ll)(1e18) + 7;
const ld eps = 1e-9;

const int B = 32;
const int N = 1000 + 3;
const int logn = 20;
const int maxn = 5e5 + 7;
/////////////////////////solve/////////////////////////

vector<int> g[maxn], gt[maxn], gc[maxn];

vector<vector<int>> t;
int comp[maxn];
vector<int> top;
bool used[maxn];
int col[maxn];

void dfs(int v) {
    used[v] = 1;
    for (auto u : g[v]) {
        if (!used[u]) dfs(u);
    }
    top.push_back(v);
}

void dfs2(int v, int k) {
    used[v] = 1;
    comp[v] = k;
    for (auto u : gt[v]) {
        if (!used[u]) dfs2(u, k);
    }
}

void dfs3(int v) {
    used[v] = 1;
    for (auto u : gc[v]) {
        if (!used[u]) dfs3(u);
    }
    // dbg(v, t[v]);
    for (auto v : t[v]) {
        if (col[v]) continue;
        bool red = 1;
        for (auto u : g[v]) {
            if (comp[v] == comp[u]) {
                if (col[u] == 1) red = 0;
            }
        }
        for (auto u : gt[v]) {
            if (comp[v] == comp[u]) {
                if (col[u] == 1) red = 0;
            }
        }
        if (red) {
            col[v] = 1;
            for (auto u : g[v]) {
                col[u] = 2;
            }
            for (auto u : gt[v]) {
                col[u] = 2;
            }
        }
        else col[v] = 2;
    }
}

void solve() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; ++i) {
        int v, u;
        cin >> v >> u;
        --v; --u;

        g[v].push_back(u);
        gt[u].push_back(v);
    }

    for (int i = 0; i < n; ++i) {
        if (!used[i]) dfs(i);
    }
    reverse(all(top));
    memset(used, 0, sizeof(used));
    int k = 0;
    for (auto v : top) {
        if (!used[v]) dfs2(v, k++);
    }

    t.resize(k);
    for (int v = 0; v < n; ++v) {
        t[comp[v]].push_back(v);
        for (auto u : g[v]) {
            if (comp[u] != comp[v]) {
                gc[comp[v]].push_back(comp[u]);
            }
        }
    }

    memset(used, 0, sizeof(used));
    for (int v = 0; v < k; ++v) {
        // dbg(v, t[v], comp[v]);
        if (!used[v]) {
            dfs3(v);
        }
    }

    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (col[i] == 1) ++ans;
    }
    cout << ans << "\n";
    for (int i = 0; i < n; ++i) {
        if (col[i] == 1) cout << i + 1 << " ";
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef ONPC
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif

    solve();
}

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