Submission #1247395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247395		clementine	Cop and Robber (BOI14_coprobber)	C++20	0 / 100	14 ms	24132 KiB

coprobber

#include "coprobber.h"
#include<bits/stdc++.h>
using namespace std;

struct Node
{
    int cop, robber;
    int type;
    Node(int c, int r, int t) : cop(c), robber(r), type(t) {}
};

//graph[cop][robber][0 = cop moves next, 1 = r]
vector<Node> graph[503][503][2];
vector<Node> reverse_graph[503][503][2];
bool can_win[503][503][2];
int deg[503][503];
int arr[503][503]; // given current move is police and arr[cop cur][r] where should cop go
int start(int n, bool A[MAX_N][MAX_N])
{
    queue<Node> q;

    // graph construction
    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j <n; j ++)
        {
            can_win[i][j][0] = can_win[i][j][1] = false;
            if(i == j)
            {
                can_win[i][j][0] = can_win[i][j][1] = true;
                q.push(Node(i, j, 0));
            }
        }
    }

    for(int i = 0; i < n; i ++) // for every cop pos
    {
        for(int j = 0; j < n; j ++) // for every r pos
        {
            for(int p = 0; p<n; p ++) // for every new position police can move to on a police move first node
            {
                if(A[i][p] == 1 || i == p)
                {
                    Node temp(p, j, 1);
                    graph[i][j][0].push_back(temp);
                    temp = Node(i, j, 0);
                    reverse_graph[p][j][1].push_back(temp);
                }
            }
            for(int c = 0; c < n; c ++) // for every possible move on the robber move first 
            {
                if(A[j][c] == 1)
                {
                    Node temp(i, c, 0);
                    graph[i][j][1].push_back(temp);
                    deg[i][j] ++;
                    temp = Node(i, j, 1);
                    reverse_graph[i][c][0].push_back(temp);
                }
            }
        }
    }

    //bfs
    while(!q.empty())
    {
        Node cur = q.front();
        q.pop();

        for(auto v : reverse_graph[cur.cop][cur.robber][cur.type])
        {
            // if this neighbour is already visited and winnable, dont consider it
            if(can_win[v.cop][v.robber][v.type] == true)
            {
                continue;
            }
            // if prev state was a cop move state and cop has agency to get to this state 
            if(v.type == 0)
            {
                can_win[v.cop][v.robber][v.type] = true;
                arr[v.cop][v.robber] = cur.cop;
                q.push(v);
            }
            else // previous state was a robber move first, - deg
            {
                deg[v.cop][v.robber] --;
                if(deg == 0)
                {
                    can_win[v.cop][v.robber][v.type] = true;
                    q.push(v);
                }
            }
        }
    }

    // determine answer and output
    int valid = true;
    for(int j = 0; j < n; j ++)
    {
        if(!can_win[0][j][0])
        {
            valid = false;
            break;
        }
    }
    
    if(valid)
    {
        return 0;
    }
    return -1;
    //bfs to determine which positions are winning positions
    // 1. create a queue with all known winning positions
    // 2. use reverse graph to find neighbours, if your neighbour is a police move first node then mark it as true, and add to bfs
    //3. if your neighbour is a rober move first node, 
    //a) keep track of its degree and -1 each time you have visited 
    // if deg == 0 then ,mark it as winning and add to queue
    // at end of bfs check and see if there exists a position i for police such that for all j for robber
    // it is winning
    // if not, return -1 else return 1
    // 4. for each winning move, keep track of where it should be headed, i.e. create an array
    // arr[i][j] given police at i, robber at j, police move, then in the reverse graph step, put the origional vertex as 
    // arr[i][j] where i is where police is at reverse_graph neighbour, j is where robber is at in rgn, p == arr[i][j] is police in graph 
}

int nextMove(int R)
{
    return 0;
}

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