oj.uz

답안 #782443

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
782443 2023-07-14T01:46:07 Z kebine Naboj (COCI22_naboj) C++17
110 / 110
 388 ms 36612 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=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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 7 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 7 ms 15956 KB Output is correct
7 Correct 7 ms 15956 KB Output is correct
8 Correct 7 ms 15964 KB Output is correct
9 Correct 7 ms 15956 KB Output is correct
10 Correct 7 ms 15956 KB Output is correct
11 Correct 7 ms 15956 KB Output is correct
12 Correct 7 ms 15956 KB Output is correct
13 Correct 7 ms 15956 KB Output is correct
14 Correct 7 ms 15956 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 217 ms 28508 KB Output is correct
2 Correct 202 ms 28608 KB Output is correct
3 Correct 108 ms 22656 KB Output is correct
4 Correct 209 ms 28656 KB Output is correct
5 Correct 227 ms 28656 KB Output is correct
6 Correct 222 ms 28628 KB Output is correct
7 Correct 203 ms 28584 KB Output is correct
8 Correct 162 ms 25148 KB Output is correct
9 Correct 218 ms 28608 KB Output is correct
10 Correct 219 ms 28580 KB Output is correct

Subtask #3
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 7 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 7 ms 15956 KB Output is correct
7 Correct 7 ms 15956 KB Output is correct
8 Correct 7 ms 15964 KB Output is correct
9 Correct 7 ms 15956 KB Output is correct
10 Correct 7 ms 15956 KB Output is correct
11 Correct 7 ms 15956 KB Output is correct
12 Correct 7 ms 15956 KB Output is correct
13 Correct 7 ms 15956 KB Output is correct
14 Correct 7 ms 15956 KB Output is correct
15 Correct 217 ms 28508 KB Output is correct
16 Correct 202 ms 28608 KB Output is correct
17 Correct 108 ms 22656 KB Output is correct
18 Correct 209 ms 28656 KB Output is correct
19 Correct 227 ms 28656 KB Output is correct
20 Correct 222 ms 28628 KB Output is correct
21 Correct 203 ms 28584 KB Output is correct
22 Correct 162 ms 25148 KB Output is correct
23 Correct 218 ms 28608 KB Output is correct
24 Correct 219 ms 28580 KB Output is correct
25 Correct 104 ms 29328 KB Output is correct
26 Correct 130 ms 28092 KB Output is correct
27 Correct 111 ms 29504 KB Output is correct
28 Correct 122 ms 32076 KB Output is correct
29 Correct 74 ms 27764 KB Output is correct
30 Correct 138 ms 31812 KB Output is correct
31 Correct 26 ms 18696 KB Output is correct
32 Correct 281 ms 28768 KB Output is correct
33 Correct 388 ms 35348 KB Output is correct
34 Correct 287 ms 29300 KB Output is correct
35 Correct 339 ms 35460 KB Output is correct
36 Correct 303 ms 28556 KB Output is correct
37 Correct 323 ms 33928 KB Output is correct
38 Correct 331 ms 32052 KB Output is correct
39 Correct 359 ms 35156 KB Output is correct
40 Correct 319 ms 33208 KB Output is correct
41 Correct 343 ms 32976 KB Output is correct
42 Correct 343 ms 36180 KB Output is correct
43 Correct 324 ms 29988 KB Output is correct
44 Correct 350 ms 36612 KB Output is correct
45 Correct 302 ms 29184 KB Output is correct
46 Correct 356 ms 33288 KB Output is correct