oj.uz

답안 #625078

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
625078 2022-08-09T10:01:21 Z chonka 경찰관과 강도 (BOI14_coprobber) C++17
0 / 100
 1 ms 336 KB 
#include<bits/stdc++.h>
#include "coprobber.h"


int n ;
int a[ MAX_N ][ MAX_N ] , deg[ MAX_N ] ;
int cnt[ MAX_N ][ MAX_N ] ;
bool dp[ MAX_N ][ MAX_N ][ 2 ] ;
bool done[ MAX_N ][ MAX_N ] ;

struct el {
    int x , y , type ;
    el ( ) { x = y = type = 0 ; }
    el ( int _x , int _y , int _type ) {
        x = _x , y = _y , type = _type ;
    }
};

int wh ;

int start(int N, bool A[MAX_N][MAX_N]) {
    n = N ;
    for ( int i = 0 ; i < n ; ++ i ) {
        for ( int j = 0 ; j < n ; ++ j ) {
            a[ i ][ j ] = A[ i ][ j ] ;
            if ( a[ i ][ j ] == 1 ) {
                ++ deg[ i ] ;
            }
        }
    }
    std :: queue < el > q ;
    for ( int i = 0 ; i < n ; ++ i ) {
        q.push ( el ( i , i , 0 ) ) ;
        q.push ( el ( i , i , 1 ) ) ;
        dp[ i ][ i ][ 0 ] = dp[ i ][ i ][ 1 ] = true ;
    }
    while ( q.empty ( ) == false ) {
        auto [ x , y , id ] = q.front ( ) ;
        q.pop ( ) ;
        for ( int z = 0 ; z < n ; ++ z ) {
            if ( id == 0 ) {
                if ( a[ y ][ z ] == 1 ) { 
                    ++ cnt[ x ][ z ] ;
                    if ( cnt[ x ][ z ] == deg[ z ] ) {
                        dp[ x ][ z ][ 1 ] = true ;
                        q.push ( el ( x , z , 1 ) ) ;
                    }
                }
            }
            else {
                if ( a[ x ][ z ] == 1 ) { 
                    if ( dp[ z ][ y ][ 0 ] == false ) {
                        dp[ z ][ y ][ 0 ] = true ;
                        q.push ( el ( z , y , 0 ) ) ;
                    }
                }
            }
        }
        if ( id == 1 && dp[ x ][ y ][ 0 ] == false ) {
            dp[ x ][ y ][ 0 ] = true ;
            q.push ( el ( x , y , 0 ) ) ;
        }
    }
    for ( int i = 0 ; i < n ; ++ i ) {
        int hh = 0 ;
        for ( int j = 0 ; j < n ; ++ j ) {
            if ( dp[ i ][ j ][ 0 ] == true ) { ++ hh ; }
        }
        if ( hh == n ) { wh = i ; return i ; }
    }
    return -1 ;
}

int nextMove ( int R ) {
    done[ wh ][ R ] = true ;
    for ( int i = 0 ; i < n ; ++ i ) {
        if ( done[ i ][ R ] == true ) { continue ; }
        if ( ( a[ wh ][ i ] == 1 || wh == i ) && dp[ i ][ R ][ 1 ] == true ) {
            wh = i ;
            return wh ;
        }
    }
    return wh ;
}

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 300 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB the situation repeated
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 300 KB the situation repeated
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Incorrect 0 ms 336 KB the situation repeated
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 300 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB the situation repeated
4 Halted 0 ms 0 KB -