oj.uz

Submission #145053

# Submission time Handle Problem Language Result Execution time Memory
145053 2019-08-18T15:19:16 Z Linca_Robert Alkemija (COCI18_alkemija) C++14
80 / 80
 192 ms 10816 KB 
#include<bits/stdc++.h>
using namespace std;

const int DIM = 1e5 + 5;

int N, cnt_ukn[DIM], M, f[DIM], K, vis[DIM];
vector<int> aux[DIM];
vector<int> R[DIM];
queue<int> q;
int main(){

    cin >> N >> M;
    for( int i = 1; i <= M; i++ ){
        int x; cin >> x;
        f[x] = 1;
    }

    cin >> K;
    for( int i = 1; i <= K; i++ ){
        int a, b; cin >> a >> b;
        cnt_ukn[i] = a;
        for( int j = 1; j <= a; j++ ){
            int x; cin >> x;
            cnt_ukn[i] -= f[x];
            if( f[x] == 0 )
                aux[x].push_back( i );
        }
        for( int j = 1; j <= b; j++ ){
            int x; cin >> x;
            R[i].push_back( x );
        }

        if( cnt_ukn[i] == 0 )
            q.push( i ), vis[i] = 1;
    }

    while( !q.empty() ){

        int curr = q.front();
        q.pop();

        for( int i = 0; i < R[curr].size(); i++ ){

            f[ R[curr][i] ] = 1;
            for( int j = 0; j < aux[ R[curr][i] ].size(); j++ ){
                int k = aux[ R[curr][i] ][j];
                cnt_ukn[k]--;
                if( cnt_ukn[k] == 0 && vis[k] == 0 ){
                    q.push( k );
                    vis[k] = 1;
                }
            }

            if( !aux[ R[curr][i] ].empty() )
                 aux[ R[curr][i] ].clear();
        }
    }

    int ans = 0;
    for( int i = 1; i <= N; i++ )
        ans += f[i];
    cout << ans << "\n";
    for( int i = 1; i <= N; i++ )
        if( f[i] == 1 )
            cout << i << " ";
    return 0;
}

Compilation message

alkemija.cpp: In function 'int main()':
alkemija.cpp:42:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for( int i = 0; i < R[curr].size(); i++ ){
                         ~~^~~~~~~~~~~~~~~~
alkemija.cpp:45:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for( int j = 0; j < aux[ R[curr][i] ].size(); j++ ){
                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct

Subtask #3
8.0 / 8.0

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

Subtask #4
8.0 / 8.0

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

Subtask #5
8.0 / 8.0

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

Subtask #6
8.0 / 8.0

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

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 6644 KB Output is correct
2 Correct 72 ms 7188 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 8624 KB Output is correct
2 Correct 146 ms 9436 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 10548 KB Output is correct
2 Correct 147 ms 8536 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 10816 KB Output is correct
2 Correct 183 ms 10764 KB Output is correct