oj.uz

Submission #963958

# Submission time Handle Problem Language Result Execution time Memory
963958 2024-04-16T05:51:16 Z becaido Povjerenstvo (COI22_povjerenstvo) C++17
100 / 100
 569 ms 152008 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 152004 KB Output is correct
2 Correct 184 ms 103124 KB Output is correct
3 Correct 19 ms 35672 KB Output is correct
4 Correct 91 ms 63228 KB Output is correct
5 Correct 155 ms 81488 KB Output is correct
6 Correct 166 ms 82360 KB Output is correct
7 Correct 124 ms 82504 KB Output is correct
8 Correct 164 ms 81548 KB Output is correct
9 Correct 330 ms 92132 KB Output is correct
10 Correct 417 ms 87636 KB Output is correct
11 Correct 458 ms 89144 KB Output is correct
12 Correct 468 ms 83168 KB Output is correct
13 Correct 326 ms 84472 KB Output is correct
14 Correct 282 ms 84576 KB Output is correct
15 Correct 243 ms 84860 KB Output is correct
16 Correct 252 ms 85076 KB Output is correct
17 Correct 52 ms 41180 KB Output is correct
18 Correct 89 ms 44824 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 151868 KB Output is correct
2 Correct 174 ms 83372 KB Output is correct
3 Correct 125 ms 80120 KB Output is correct
4 Correct 461 ms 87896 KB Output is correct
5 Correct 569 ms 89380 KB Output is correct
6 Correct 303 ms 86480 KB Output is correct
7 Correct 299 ms 86612 KB Output is correct
8 Correct 262 ms 86356 KB Output is correct
9 Correct 232 ms 85588 KB Output is correct
10 Correct 53 ms 40776 KB Output is correct
11 Correct 53 ms 41844 KB Output is correct
12 Correct 54 ms 41832 KB Output is correct
13 Correct 190 ms 135356 KB Output is correct
14 Correct 171 ms 91264 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 36624 KB Output is correct
2 Correct 21 ms 35968 KB Output is correct
3 Correct 20 ms 35928 KB Output is correct
4 Correct 21 ms 36036 KB Output is correct
5 Correct 22 ms 36232 KB Output is correct
6 Correct 21 ms 36164 KB Output is correct
7 Correct 21 ms 36184 KB Output is correct
8 Correct 21 ms 35968 KB Output is correct
9 Correct 22 ms 35676 KB Output is correct
10 Correct 19 ms 35676 KB Output is correct
11 Correct 19 ms 35676 KB Output is correct
12 Correct 21 ms 36696 KB Output is correct
13 Correct 20 ms 36344 KB Output is correct
14 Correct 19 ms 35780 KB Output is correct
15 Correct 21 ms 36188 KB Output is correct
16 Correct 22 ms 36188 KB Output is correct
17 Correct 22 ms 36188 KB Output is correct
18 Correct 20 ms 35800 KB Output is correct
19 Correct 20 ms 35932 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 152004 KB Output is correct
2 Correct 184 ms 103124 KB Output is correct
3 Correct 19 ms 35672 KB Output is correct
4 Correct 91 ms 63228 KB Output is correct
5 Correct 155 ms 81488 KB Output is correct
6 Correct 166 ms 82360 KB Output is correct
7 Correct 124 ms 82504 KB Output is correct
8 Correct 164 ms 81548 KB Output is correct
9 Correct 330 ms 92132 KB Output is correct
10 Correct 417 ms 87636 KB Output is correct
11 Correct 458 ms 89144 KB Output is correct
12 Correct 468 ms 83168 KB Output is correct
13 Correct 326 ms 84472 KB Output is correct
14 Correct 282 ms 84576 KB Output is correct
15 Correct 243 ms 84860 KB Output is correct
16 Correct 252 ms 85076 KB Output is correct
17 Correct 52 ms 41180 KB Output is correct
18 Correct 89 ms 44824 KB Output is correct
19 Correct 215 ms 151868 KB Output is correct
20 Correct 174 ms 83372 KB Output is correct
21 Correct 125 ms 80120 KB Output is correct
22 Correct 461 ms 87896 KB Output is correct
23 Correct 569 ms 89380 KB Output is correct
24 Correct 303 ms 86480 KB Output is correct
25 Correct 299 ms 86612 KB Output is correct
26 Correct 262 ms 86356 KB Output is correct
27 Correct 232 ms 85588 KB Output is correct
28 Correct 53 ms 40776 KB Output is correct
29 Correct 53 ms 41844 KB Output is correct
30 Correct 54 ms 41832 KB Output is correct
31 Correct 190 ms 135356 KB Output is correct
32 Correct 171 ms 91264 KB Output is correct
33 Correct 20 ms 36624 KB Output is correct
34 Correct 21 ms 35968 KB Output is correct
35 Correct 20 ms 35928 KB Output is correct
36 Correct 21 ms 36036 KB Output is correct
37 Correct 22 ms 36232 KB Output is correct
38 Correct 21 ms 36164 KB Output is correct
39 Correct 21 ms 36184 KB Output is correct
40 Correct 21 ms 35968 KB Output is correct
41 Correct 22 ms 35676 KB Output is correct
42 Correct 19 ms 35676 KB Output is correct
43 Correct 19 ms 35676 KB Output is correct
44 Correct 21 ms 36696 KB Output is correct
45 Correct 20 ms 36344 KB Output is correct
46 Correct 19 ms 35780 KB Output is correct
47 Correct 21 ms 36188 KB Output is correct
48 Correct 22 ms 36188 KB Output is correct
49 Correct 22 ms 36188 KB Output is correct
50 Correct 20 ms 35800 KB Output is correct
51 Correct 20 ms 35932 KB Output is correct
52 Correct 211 ms 152008 KB Output is correct
53 Correct 184 ms 83404 KB Output is correct
54 Correct 122 ms 80316 KB Output is correct
55 Correct 440 ms 87892 KB Output is correct
56 Correct 560 ms 89272 KB Output is correct
57 Correct 340 ms 86408 KB Output is correct
58 Correct 288 ms 86628 KB Output is correct
59 Correct 258 ms 86472 KB Output is correct
60 Correct 55 ms 41120 KB Output is correct
61 Correct 62 ms 41848 KB Output is correct
62 Correct 55 ms 41744 KB Output is correct
63 Correct 192 ms 135700 KB Output is correct
64 Correct 164 ms 89832 KB Output is correct
65 Correct 62 ms 42148 KB Output is correct
66 Correct 497 ms 84912 KB Output is correct
67 Correct 315 ms 85564 KB Output is correct
68 Correct 272 ms 84884 KB Output is correct
69 Correct 57 ms 41140 KB Output is correct
70 Correct 123 ms 65744 KB Output is correct