Submission #782443

#	Time	Username	Problem	Language	Result	Execution time	Memory
782443		kebine	Naboj (COCI22_naboj)	C++17	110 / 110	388 ms	36612 KiB

naboj

#include <bits/stdc++.h>
using namespace std;
 
#define v          vector
#define int        long long
#define all(a)     (a).begin(), (a).end()
#define pb         push_back
#define mk         make_pair
#define pii        pair<int, int>
#define ff         first
#define ss         second
#define inp_v(vec) for (auto &i : vec) cin >> i;
#define prt_v(vec) for (auto i : vec) cout << i << endl;
#define MS(x)     memset(x, 0, sizeof(x))
#define gcd(a,b)   __gcd(a, b);
#define lcm(a,b)   (a*(b/gcd(a,b)))
#define lb         lower_bound
#define ub         upper_bound
bool chmin(int &a, int b){return b<a?a=b, true:false;}
bool chmax(int &a, int b){return b>a?a=b, true:false;}
const int maxn=5e5+5;
vector<int>adj[maxn];
bool vis[maxn];
vector<int>val(maxn);
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int N, M;cin>>N>>M;
    vector<pair<int, int>>A(M+1);
    // vector<int>val(N+1);
    for(int i=0;i<M;i++){
        cin>>A[i].first>>A[i].second;
        adj[A[i].first].push_back(A[i].second);
        val[A[i].second]++;
    }
    queue<int>q;
    vector<pair<int, int>>ans;
    for(int i=1;i<=N;i++){
        if(!val[i]){
            q.push(i);
            // ans.push_back({i, 0});
            vis[i]=true;
        }
    }
    while(!q.empty()){
        int p=q.front();
        q.pop();
        for(auto i:adj[p]){
            val[i]--;
            if(!val[i]){
                q.push(i);
                ans.push_back({i, 0});
            }
        }
    }
    bool stat=true;
    for(int i=1;i<=N;i++){
        // cout<<i<<" "<<val[i]<<endl;
        if(val[i])stat=false;
    }
    // stat=true;
    if(!stat)cout<<-1<<endl;
    else{
        cout<<ans.size()<<endl;
        for(auto i:ans){
            cout<<i.first<<" "<<i.second<<endl;
        }
    }
    return 0;
}

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