oj.uz

Submission #50076

# Submission time Handle Problem Language Result Execution time Memory
50076 2018-06-07T12:35:02 Z chonka Alkemija (COCI18_alkemija) C++
80 / 80
 92 ms 17368 KB 
#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std ;

#define MAXN 100007

int n , m ;
bool fl[ MAXN ] ;


vector < int > v[ MAXN ] ;

int lft[ MAXN ] ;
vector < int > aux[ MAXN ] ;

void input ( ) {
    int k ;
    scanf ( "%d%d" , &n , &k ) ;
    int i , j ;
    while ( k -- ) {
        int x ;
        scanf ( "%d" , &x ) ;
        fl[ x ] = true ;
    }
    scanf ( "%d" , &m ) ;
    for ( i = 1 ; i <= m ; i ++ ) {
        int sz1 , sz2 ;
        scanf ( "%d%d" , &sz1 , &sz2 ) ;
        for ( j = 0 ; j < sz1 ; j ++ ) {
            int x ;
            scanf ( "%d" , &x ) ;
            if ( fl[ x ] == false ) { lft[ i ] ++ ; v[ x ].push_back ( i ) ; }
        }
        for ( j = 0 ; j < sz2 ; j ++ ) {
            int x ;
            scanf ( "%d" , &x ) ;
            aux[ i ].push_back ( x ) ;
        }
    }
}

void solve ( ) {
    queue < int > q ;
    while ( q.empty ( ) == false ) { q.pop ( ) ; }
    int i , j ;
    for ( i = 1 ; i <= m ; i ++ ) {
        if ( lft[ i ] == 0 ) { q.push ( i ) ; lft[ i ] = -1 ; }
    }

    while ( q.empty ( ) == false ) {
        int x = q.front ( ) ;
        q.pop ( ) ;
        int sz = aux[ x ].size ( ) ;
        for ( i = 0 ; i < sz ; i ++ ) {
            if ( fl[ aux[ x ][ i ] ] == false ) {
                fl[ aux[ x ][ i ] ] = true ;
                int g = v[ aux[ x ][ i ] ].size ( ) ;
                for ( j = 0 ; j < g ; j ++ ) {
                    int h = v[ aux[ x ][ i ] ][ j ] ;
                    lft[ h ] -- ;
                    if ( lft[ h ] == 0 ) {
                        lft[ h ] = -1 ;
                        q.push ( h ) ;
                    }
                }
            }
        }
    }
    int ans = 0 ;
    for ( i = 1 ; i <= n ; i ++ ) {
        ans += fl[ i ] ;
    }
    printf ( "%d\n" , ans ) ;
    for ( i = 1 ; i <= n ; i ++ ) {
        if ( fl[ i ] == true ) { printf ( "%d " , i ) ; }
    }
    printf ( "\n" ) ;
}

int main ( ) {
    input ( ) ;
    solve ( ) ;
    return 0 ;
}

Compilation message

alkemija.cpp: In function 'void input()':
alkemija.cpp:19:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d%d" , &n , &k ) ;
     ~~~~~~^~~~~~~~~~~~~~~~~~~~
alkemija.cpp:23:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d" , &x ) ;
         ~~~~~~^~~~~~~~~~~~~
alkemija.cpp:26:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d" , &m ) ;
     ~~~~~~^~~~~~~~~~~~~
alkemija.cpp:29:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d%d" , &sz1 , &sz2 ) ;
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
alkemija.cpp:32:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf ( "%d" , &x ) ;
             ~~~~~~^~~~~~~~~~~~~
alkemija.cpp:37:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf ( "%d" , &x ) ;
             ~~~~~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
8.0 / 8.0

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

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5296 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5296 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6672 KB Output is correct
2 Correct 44 ms 7608 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 9208 KB Output is correct
2 Correct 78 ms 11216 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 13268 KB Output is correct
2 Correct 58 ms 13268 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 16048 KB Output is correct
2 Correct 80 ms 17368 KB Output is correct