oj.uz

Submission #781772

# Submission time Handle Problem Language Result Execution time Memory
781772 2023-07-13T10:45:22 Z makanhulia Naboj (COCI22_naboj) C++17
25 / 110
 424 ms 26868 KB 
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int,int>
#define fr first
#define sc second
using namespace std;

const int N = 2e5+5;
const int M = 5e5+5;

vector<int> adj[N];
vector<int> opp[N];
vector<int> marker;
vector<int> par;
vector<int> keep;
vector<bool> vis;

bool dfs(int x) {
    marker[x] = 1;
    for (auto item : adj[x]) {
        if (!marker[item]) {
            par[item] = x;
            if (dfs(item)) return true;
        } else if (marker[item] == 1) return true;
    }
    marker[x] = 2;
    return false;
}

signed main() { 
    int n, m; cin >> n >> m;
    marker.assign(n+1, 0);
    par.assign(n+1, -1);
    vis.assign(n+1, 0);
    vector<pii> v;
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        adj[b].pb(a);
        opp[a].pb(b);
    }
    for (int i = 1; i <= n; i++) {
        if (!marker[i]) {
            if (dfs(i)) {
                cout << -1 << endl;
                return 0;
            }
        }
    }
    
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            queue<int> q;
            q.push(i);

            while(!q.empty()) {
                int cur = q.front(); q.pop();
                vis[cur] = 1;
                if (adj[cur].size() == 0) {
                    for (auto item : opp[cur]) {
                        if (!vis[item]) {
                            q.push(item);
                            v.pb({item, 0});
                        }
                    }
                } else if (opp[cur].size() == 0) {
                    for (auto item : adj[cur]) {
                        if (!vis[item]) {
                            q.push(item);
                            v.pb({item, 1});
                        }
                    }
                }
                else {
                    bool pushed = false;
                    for (auto item : adj[cur]) {
                        if (!vis[item]) {
                            pushed = true;
                            q.push(item);
                            v.pb({item, 1});
                        }
                    }
                    if (pushed) {
                        for (auto item : opp[cur]) {
                            if (!vis[item]) {
                                q.push(item);
                                v.pb({item, 0});
                            }
                        }
                    } else {
                        bool pulled = false;
                        for (auto item : opp[cur]) {
                            if (!vis[item]) {
                                pulled = true;
                                q.push(item);
                                v.pb({item, 0});
                            }
                        }
                        if (pulled) {
                            for (auto item : adj[cur]) {
                                if (!vis[item]) {
                                    q.push(item);
                                    v.pb({item, 1});
                                }
                            }
                        }
                    }
                }
            }

        }
    }
    cout << v.size() << endl;
    for (auto item : v) cout << item.fr << " " << item.sc << endl;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 5 ms 9660 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Incorrect 6 ms 9652 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 26688 KB Output is correct
2 Correct 415 ms 26780 KB Output is correct
3 Correct 185 ms 18620 KB Output is correct
4 Correct 388 ms 26748 KB Output is correct
5 Correct 376 ms 26756 KB Output is correct
6 Correct 396 ms 26752 KB Output is correct
7 Correct 424 ms 26868 KB Output is correct
8 Correct 346 ms 23340 KB Output is correct
9 Correct 386 ms 26716 KB Output is correct
10 Correct 380 ms 26652 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 5 ms 9660 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Incorrect 6 ms 9652 KB Output isn't correct
9 Halted 0 ms 0 KB -