Submission #671271

#	Time	Username	Problem	Language	Result	Execution time	Memory
671271		mdn2002	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	648 ms	9004 KiB

coprobber

#include<bits/stdc++.h>
using namespace std;
int n , iswin [502][502][3] , nxt [502][502][3] , cnt [502][502] , cur;
bool a [500][500];
int start(int N, bool A [500][500])
{
    memset ( nxt , -1 , sizeof nxt );
    n = N;
    vector < pair < pair < int , int > , int > > v;
    for ( int i = 0 ; i < n ; i ++ )
    {
        int cntt = 0;
        for ( int j = 0 ; j < n ; j ++ )
        {
            cntt += A [i][j];
            a [i][j] = A [i][j];
        }
        for ( int j = 0 ; j < n ; j ++ ) cnt [j][i] = cntt;
        iswin [i][i][0] = 1;
        iswin [i][i][1] = 1;
        v . push_back ( { { i , i } , 0 } );
        v . push_back ( { { i , i } , 1 } );
    }

    while ( v . size () )
    {
        int did = 0;
        pair < pair < int , int > , int > p = * -- v . end ();
        v . pop_back ();
        int i = p . first . first , j = p . first . second , z = p . second;
        for ( int k = 0 ; k < n ; k ++ )
        {
            int nx = i , ny = j , can = 0 , zz = z ^ 1;
            if ( zz == 1 )
            {
                ny = k;
                if ( a [j][k] ) can = 1;
            }
            else
            {
                nx = k;
                if ( a [i][k] ) can = 1;
            }
            if ( zz == 0 && i == k ) can = 1;
            if ( can == 0 || iswin [nx][ny][zz] ) continue;
            if ( zz == 0 )
            {
                iswin [nx][ny][zz] = 1;
                nxt [nx][ny][zz] = i;
                v . push_back ( { { nx , ny } , zz } );
            }
            else
            {
                cnt [nx][ny] --;
                if ( cnt [nx][ny] == 0 )
                {
                    nxt [nx][ny][zz] = j;
                    iswin [nx][ny][zz] = 1;
                    v . push_back ( { { nx , ny } , zz } );
                }
            }
        }
    }
    for ( int i = 0 ; i < n ; i ++ )
    {
        int num = 0;
        for ( int j = 0 ; j < n ; j ++ )
        {
            if ( iswin [i][j][0] ) num ++;
        }
        if ( num == n )
        {
            cur = i;
            return i;
        }
    }
    return -1;
}


int nextMove(int R) {
    if ( cur == -1 ) return -1;
    cur = nxt [cur][R][0];
    return cur;
}

/*
int main()
{
    cin >> n;
    for ( int i = 0 ; i < n ; i ++ )
    {
        for ( int j = 0 ; j < n ; j ++ ) cin >> a [i][j];
    }

    cout << start ( n , a ) << endl;
    for ( int i = 0 ; i < n ; i ++ )
    {
        for ( int j = 0 ; j < n ; j ++ )
        {
            if ( iswin [i][j] ) cout << ' ' << i << ' ' << j << endl;
        }
    }
    while ( true )
    {
        int x;
        cin >> x;
        cout << ' ' << nextMove ( x ) << endl;
    }
}
*/

Compilation message (stderr)

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:27:13: warning: unused variable 'did' [-Wunused-variable]
   27 |         int did = 0;
      |             ^~~

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