oj.uz

Submission #144799

# Submission time Handle Problem Language Result Execution time Memory
144799 2019-08-17T19:17:06 Z radugheo Alkemija (COCI18_alkemija) C++14
80 / 80
 195 ms 10596 KB 
#include <bits/stdc++.h>
#define DIM 100005

using namespace std;

struct react{
    int a;
    int b;
    int necunoscute;
    vector <int> p;
};

react r[DIM];
deque <int> q;
vector <int> l[DIM];
bitset <DIM> f, viz;

int n, m, x, i, j, k, reactie, nod, sol, rr;

int main(){
    cin >> n >> m;
    for (i=1; i<=m; i++){
        cin >> x;
        f[x] = 1;
    }
    cin >> k;
    for (i=1; i<=k; i++){
        cin >> r[i].a >> r[i].b;
        r[i].necunoscute = r[i].a;
        for (j=1; j<=r[i].a; j++){
            cin >> x;
            l[x].push_back(i);
            if (f[x] == 1){
                r[i].necunoscute--;
                if (r[i].necunoscute == 0){
                    q.push_back(i);
                    viz[i] = 1;
                }
            }
        }
        for (j=1; j<=r[i].b; j++){
            cin >> x;
            r[i].p.push_back(x);
        }
    }
    while (!q.empty()){
        nod = q.front();
        q.pop_front();
        for (i=0; i<r[nod].p.size(); i++){
            rr = r[nod].p[i];
            if (f[rr] == 0){
                f[rr] = 1;
                for (j=0; j<l[rr].size(); j++){
                    reactie = l[rr][j];
                    if (viz[reactie] == 0){
                        r[reactie].necunoscute--;
                        if (r[reactie].necunoscute == 0){
                            q.push_back(reactie);
                            viz[reactie] = 1;
                        }
                    }
                }
            }
        }
    }
    for (i=1; i<=n; i++){
        if (f[i] == 1)
            sol++;
    }
    cout << sol << "\n";
    for (i=1; i<=n; i++){
        if (f[i] == 1){
            cout << i << " ";
        }
    }
    return 0;
}

Compilation message

alkemija.cpp: In function 'int main()':
alkemija.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0; i<r[nod].p.size(); i++){
                   ~^~~~~~~~~~~~~~~~
alkemija.cpp:53:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (j=0; j<l[rr].size(); j++){
                           ~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6648 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6520 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6648 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6520 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6524 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6520 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 7628 KB Output is correct
2 Correct 77 ms 7972 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 9120 KB Output is correct
2 Correct 149 ms 9480 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 10132 KB Output is correct
2 Correct 169 ms 9436 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 10596 KB Output is correct
2 Correct 185 ms 10080 KB Output is correct