oj.uz

Submission #781596

# Submission time Handle Problem Language Result Execution time Memory
781596 2023-07-13T08:29:58 Z andecaandeci Naboj (COCI22_naboj) C++17
0 / 110
 384 ms 25676 KB 
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int, int>
#define uh pair<int,pii>
#define fr first
#define sc second
#define all(x) x.begin(), x.end()
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<bool> sequenced;
vector<vector<int>> ano;

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);
    sequenced.assign(n+1, 0);
    // if going forward then 

    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 (opp[i].size() and adj[i].size() and !sequenced[i]) {
            vector<int> v;
            queue<int> q;
            v.pb(i);
            q.push(i);
            while(!q.empty()) {
                int cur = q.front(); q.pop();
                sequenced[cur] = 1;
                for (auto item : opp[cur]) {
                    if (!sequenced[item] and opp[item].size()) {
                        q.push(item);
                        v.pb(item);
                    }

                }
            }
            reverse(v.begin(), v.end());
            q.push(i);
            while(!q.empty()) {
                int cur = q.front(); q.pop();
                sequenced[cur] = 1;
                for (auto item : adj[cur]) {
                    if (!sequenced[item] and adj[item].size()) {
                        q.push(item);
                        v.pb(item);
                    }
                }
            }
            ano.pb(v);
        }
    }

    cout << n << endl;
    for (auto vec : ano) {
        for (auto item : vec) cout << item << " " << 1 << endl;
    }
    for (int i = n; i >= 1; i--) {
        if (!sequenced[i]) {
            cout << i << " " << (adj[i].size() == 0) << endl;
        }
    }
}

Subtask #1
0 / 15.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 384 ms 25676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

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