Submission #77808

#	Time	Username	Problem	Language	Result	Execution time	Memory
77808		Charis02	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	450 ms	7772 KiB

coprobber

#include "coprobber.h"
#include<iostream>
#include<vector>
#include<queue>
#define rep(i,a,b) for(int i = a;i < b;i++)
#define MAX_N 500
#define ll long long

using namespace std;

struct state{
    int who; // 0 - cop plays next, 1 rob plays next
    int cop;
    int rob;
};

int leftToWin[MAX_N][MAX_N][2],nextPos[MAX_N][MAX_N],curpos=0;

int start(int N, bool A[MAX_N][MAX_N])
{
    rep(i,0,N)
    {
        int deg = 0;

        rep(j,0,N)
        {
            if(A[i][j])
                deg++;
        }

        rep(j,0,N)
        {
            if(i != j)
            {
                leftToWin[j][i][0] = 1;
                leftToWin[j][i][1] = deg;
            }
        }
    }

    queue < state > q;

    rep(i,0,N)
    {
        state s;
        s.cop = i;
        s.rob = i;
        s.who = 0;

        q.push(s);

        s.who = 1;

        q.push(s);
    }

    int totalstates = 0;

    while(!q.empty())
    {
        state cur = q.front();
        q.pop();
        totalstates++;

       // cout << cur.cop << " " << cur.rob << " " << cur.who << endl;

        if(cur.who == 0)
        {
            rep(i,0,N)
            {
                if(A[i][cur.rob] && leftToWin[cur.cop][i][1] != 0)
                {
                    leftToWin[cur.cop][i][1]--;

                    if(leftToWin[cur.cop][i][1] == 0)
                    {
                        state neo = cur;
                        neo.rob = i;
                        neo.who = 1;

                        q.push(neo);
                    }
                }
            }
        }
        else
        {
            rep(i,0,N)
            {
                if((A[cur.cop][i] || cur.cop == i)  && leftToWin[i][cur.rob][0] != 0)
                {
                    leftToWin[i][cur.rob][0] = 0;

                    state neo = cur;
                    neo.cop = i;
                    neo.who = 0;

                    q.push(neo);
                    nextPos[i][cur.rob] = cur.cop;
                }
            }
        }
    }

    return totalstates == 2*N*N ? 0 : -1;
}

int nextMove(int R)
{
    return curpos = nextPos[curpos][R];
}
/*
int main()
{
    int n;
    cin >> n;
    bool a[MAX_N][MAX_N];
    rep(i,0,n)
    {
        rep(j,0,n)
        {
            cin >> a[i][j];
        }
    }

    cout<<start(n,a) << endl;

    while(true)
    {
        int x;
        cin >> x;

        cout << nextMove(x) << endl;
    }
}
*/

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