Submission #625094

#	Time	Username	Problem	Language	Result	Execution time	Memory
625094		chonka	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	521 ms	8080 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 ] ;
int nxt[ 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 ;
                        nxt[ z ][ y ] = x ;
                        q.push ( el ( z , y , 0 ) ) ;
                    }
                }
            }
        }
        if ( id == 1 && dp[ x ][ y ][ 0 ] == false ) {
            dp[ x ][ y ][ 0 ] = true ;
            nxt[ x ][ y ] = x ;
            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 ) {
    wh = nxt[ wh ][ R ] ;
    return wh ;
}

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