Submission #625085

#	Time	Username	Problem	Language	Result	Execution time	Memory
625085		chonka	Cop and Robber (BOI14_coprobber)	C++17	0 / 100	302 ms	4124 KiB

coprobber

#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 ][ 2 ] ;

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 ][ 0 ] = true ;
    for ( int i = 0 ; i < n ; ++ i ) {
        if ( done[ i ][ R ][ 1 ] == true ) { continue ; }
        if ( ( a[ wh ][ i ] == 1 || wh == i ) && dp[ i ][ R ][ 1 ] == true ) {
            bool ok = true ;
            for ( int j = 0 ; j < n ; ++ j ) {
                if ( a[ R ][ j ] == 0 || j == i ) { continue ; }
                if ( done[ i ][ j ][ 0 ] == true ) { ok = false ; break ; }
            }
            if ( ok == true ) { 
                wh = i ;
                done[ wh ][ R ][ 1 ] = true ;
                return wh ;
            }
        }
    }
    return wh ;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 14
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40