oj.uz

Submission #144552

# Submission time Handle Problem Language Result Execution time Memory
144552 2019-08-17T07:05:17 Z mirceaishere Alkemija (COCI18_alkemija) C++14
80 / 80
 202 ms 12808 KB 
#include <iostream>
#include <vector>
using namespace std;

/// in f[k] verific daca am descoperit elementul k
/// in viz[k] verific daca am folosit reactia k (ar fi inutil sa o repetam)
/// in cauta tin pe randul k indicele reactiilor care il folosesc pe k

struct reactie{
    int r; /// nr elemente cerute
    int l; /// nr elemente rezultate
    int x; /// nr elemente inca neobtinute
    vector<int>y; /// elementele rezultate
}v[100010];

int n, m, x, k, i, j, f[100010], viz[100010], c[100010], p, u, elem, r, rc, sol;
vector<int>cauta[100010];

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>>v[i].l>>v[i].r;
        v[i].x=v[i].l;
        for(j=1; j<=v[i].l; j++){
            cin>>x;
            cauta[x].push_back(i);
            if(f[x]==1){
                v[i].x--;
                if(v[i].x==0){
                    u++;
                    c[u]=i;
                    viz[i]=1;
                }
            }
        }
        for(j=1; j<=v[i].r; j++){
            cin>>x;
            v[i].y.push_back(x);
        }
    }
    p=1;
    while(p<=u){
        r=c[p];
        /// fac reactia r si marchez elementele noi
        for(i=0; i<v[r].y.size(); i++){
            elem=v[r].y[i];
            if(f[elem]==0){
                f[elem]=1;
                for(j=0; j<cauta[elem].size(); j++){
                    /// elementul obtinut face parte din reactia curenta (rc)
                    rc=cauta[elem][j];
                    if(viz[rc]==0){
                        v[rc].x--;
                        if(v[rc].x==0){
                            u++;
                            c[u]=rc;
                            viz[rc]=1;
                        }
                    }
                }
            }
        }
        p++;
    }
    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<<" ";
        }
    }
}

Compilation message

alkemija.cpp: In function 'int main()':
alkemija.cpp:50:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0; i<v[r].y.size(); i++){
                  ~^~~~~~~~~~~~~~
alkemija.cpp:54:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(j=0; j<cauta[elem].size(); j++){
                          ~^~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
8.0 / 8.0

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

Subtask #5
8.0 / 8.0

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

Subtask #6
8.0 / 8.0

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

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8172 KB Output is correct
2 Correct 76 ms 8800 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 10444 KB Output is correct
2 Correct 146 ms 11108 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 12256 KB Output is correct
2 Correct 165 ms 11216 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 12808 KB Output is correct
2 Correct 187 ms 12252 KB Output is correct