Submission #782435

#	Time	Username	Problem	Language	Result	Execution time	Memory
782435		makanhulia	Naboj (COCI22_naboj)	C++17	110 / 110	628 ms	38016 KiB

naboj

#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;
vector<int> v;

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;
}

void dfs2(int x) {
    vis[x] = 1;
    for (auto item : adj[x]) {
        if (!vis[item] and adj[item].size() and opp[item].size())
            dfs2(item);
    }
    v.push_back(x);
}

signed main() { 
    int n, m; cin >> n >> m;
    marker.assign(n+1, 0);
    par.assign(n+1, -1);
    vis.assign(n+1, 0);

    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;
            }
        }
    }
    vis.assign(n+1, 0);
    for (int i = 1; i <= n; i++) {
        if (!vis[i] and adj[i].size() and opp[i].size())
            dfs2(i);
    }
    
    reverse(v.begin(), v.end());
    cout << n << endl;
    for (auto item : v) {
        cout << item << " " << 1 << endl;
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            cout << i << " " << (adj[i].size() == 0) << endl;
        }
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 25 / 25
• Subtask 3: 70 / 70