oj.uz

Submission #635535

# Submission time Handle Problem Language Result Execution time Memory
635535 2022-08-26T11:36:15 Z _HDH Naboj (COCI22_naboj) C++11
0 / 110
 194 ms 19776 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
int const N = 2e5 + 1;
 
vector<int> g[N], h[N];
 
int main(){
    int n, m; cin >> n >> m;
    while (m--){
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        h[b].push_back(a);
    }
 
    int sign[N] = {};
    memset(sign, -1, sizeof sign);
 
    for (int i = 1; i <= n; i++){
        if (g[i].size() > 0 && h[i].size() > 0){
            for (auto v: g[i]){
                if (sign[v] == 1){
                    cout << -1;
                    return 0;
                }
                sign[v] = 0;
            }
            for (auto v: h[i]){
                if (sign[v] == 0){
                    cout << -1;
                    return 0;
                }
                sign[v] = 1;
            }
        }
    }
 
    for (int i = 1; i <= n; i++) if (sign[i] == -1){
        if (g[i].size() > 0 && h[i].size() == 0){
            bool flag = 0;
            for (auto v: g[i]){
                if (sign[v] == 1){
                    cout << -1;
                    return 0;
                }
                if (sign[v] == 0)
                    flag = 1;
            }
 
            if (flag)
                for (auto v: g[i]){
                    sign[v] = 0;
                }
            else{
                sign[i] = 1;
            }
        }else if (g[i].size() == 0 && h[i].size() > 0){
            bool flag = 0;
            for (auto v: h[i]){
                if (sign[v] == 0){
                    cout << -1;
                    return 0;
                }
                if (sign[v] == 1)
                    flag = 1;
            }
 
            if (flag)
                for (auto v: h[i])
                    sign[v] = 1;
            else sign[i] = 0;
        }
    }
 
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (sign[i] != -1) cnt++;
    cout << cnt << "\n";
    for (int i = 1; i <= n; i++)
        if (sign[i] != -1) cout << i << " " << sign[i] << "\n";
    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 8 ms 10476 KB Output is correct
3 Correct 6 ms 10472 KB Output is correct
4 Correct 5 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Incorrect 7 ms 10476 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

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

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 8 ms 10476 KB Output is correct
3 Correct 6 ms 10472 KB Output is correct
4 Correct 5 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Incorrect 7 ms 10476 KB Output isn't correct
9 Halted 0 ms 0 KB -