oj.uz

Submission #782440

# Submission time Handle Problem Language Result Execution time Memory
782440 2023-07-14T01:40:50 Z kebine Naboj (COCI22_naboj) C++17
15 / 110
 1000 ms 15064 KB 
#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=2e5+5;
vector<int>adj[maxn];
bool vis[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]--;
        }
        for(int i=1;i<=N;i++){
            if(!val[i]&&!vis[i]){
                vis[i]=true;
                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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 5020 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4952 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 5024 KB Output is correct
14 Correct 2 ms 4948 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 15064 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 5020 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4952 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 5024 KB Output is correct
14 Correct 2 ms 4948 KB Output is correct
15 Execution timed out 1074 ms 15064 KB Time limit exceeded
16 Halted 0 ms 0 KB -