# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
50076 | 2018-06-07T12:35:02 Z | chonka | Alkemija (COCI18_alkemija) | C++ | 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4984 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5100 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5100 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5100 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 5296 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 5296 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 24 ms | 6672 KB | Output is correct |
2 | Correct | 44 ms | 7608 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 54 ms | 9208 KB | Output is correct |
2 | Correct | 78 ms | 11216 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 75 ms | 13268 KB | Output is correct |
2 | Correct | 58 ms | 13268 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 92 ms | 16048 KB | Output is correct |
2 | Correct | 80 ms | 17368 KB | Output is correct |