Submission #1247429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247429		clementine	Cop and Robber (BOI14_coprobber)	C++20	60 / 100	680 ms	327680 KiB

coprobber

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


template<typename T>
void _debug_cerr(const char* name, T&& value) {
    cerr << name << ": " << value << '\n';
}

template<typename T, typename... Args>
void _debug_cerr(const char* names, T&& value, Args&&... args) {
    const char* comma = strchr(names, ',');
    cerr.write(names, comma - names) << ": " << value << ", ";
    _debug_cerr(comma + 1, forward<Args>(args)...);
}

#define debug(...) _debug_cerr(#__VA_ARGS__, __VA_ARGS__)



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 police_current;

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, 1));
                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
        {
            if(i == j){continue;}
            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);
                }
            }
        }
    }
    /*
    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < n; j ++)
        {
            debug(i, j);
            for(auto v: reverse_graph[i][j][0])
            {
                debug(v.cop, v.robber, v.type);
            }
        }
    }
    cerr << " roober mover \n";
    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < n; j ++)
        {
            debug(i, j);
            for(auto v: reverse_graph[i][j][1])
            {
                debug(v.cop, v.robber, v.type);
            }
        }
    }
    */
    //bfs
    while(!q.empty())
    {
        Node cur = q.front();
        q.pop();
        //debug(cur.cop, cur.robber, cur.type);
        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;
            }
            //debug(v.cop, v.robber, v.type);
            // 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;
                //debug(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
            {
                //debug(deg[v.cop][v.robber]);
                deg[v.cop][v.robber] --;
                if(deg[v.cop][v.robber]== 0)
                {
                    //debug(can_win[v.cop][v.robber][v.type] = true);
                    can_win[v.cop][v.robber][v.type] = true;
                    q.push(v);
                }
            }
        }
    }

    // determine answer and output
    bool valid = true;
    for(int i = 0; i < n; i ++)
    {
        valid = true;
        police_current = i;
        for(int j = 0; j < n; j ++)
        {
            if(!can_win[i][j][0])
            {
                valid = false;
                break;
            }
        }
    }
    
    if(valid)
    {
        return police_current;
    }
    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)
{
    int temp = police_current;
    police_current = arr[police_current][R];
    debug(temp, R, police_current);
    return police_current;
}

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