Submission #71364

#	Time	Username	Problem	Language	Result	Execution time	Memory
71364		someone_aa	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	744 ms	8316 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 510;
bool visited[maxn][maxn][2];
bool a[maxn][maxn];
int n;

int lf[maxn][maxn][2];
int nxt[maxn][maxn];

struct state {
    int c, r, t;
};

int curr;

int start(int N, bool A[MAX_N][MAX_N]) {
    queue<state>q;
    for(int c=0;c<N;c++) {
        for(int r=0;r<N;r++) {
            if(c!=r) {
                lf[c][r][0] = 1;
                lf[c][r][1] = count(A[r], A[r]+N, true);
            }
        }
        q.push({c,c,0});
        q.push({c,c,1});
    }

    int calls = 0;
    while(!q.empty()) {
        state curr = q.front();
        q.pop();

        //if(curr.c == 0)
          //  cout<<curr.c<<" "<<curr.r<<" Last was: "<<curr.t<<" -> \n";

        visited[curr.c][curr.r][curr.t] = true;
        calls++;
        if(curr.t) {
            for(int i=0;i<N;i++) {
                if((i==curr.c || A[curr.c][i]) && lf[i][curr.r][0]) {
                    //if(curr.c == 0)
                      //  cout<<"calling: "<<i<<"with state 0"<<"\n";
                    lf[i][curr.r][0] = 0;
                    q.push({i, curr.r, 0});
                    nxt[i][curr.r] = curr.c;
                }
            }
        }
        else {
            for(int i=0;i<N;i++) {
                if(A[curr.r][i] && lf[curr.c][i][1]) {
                    //if(curr.c == 0)
                      //  cout<<"calling: "<<i<<"with state 1"<<" left: "<<lf[curr.c][i][1]<<"\n";
                    lf[curr.c][i][1]--;
                    if(lf[curr.c][i][1] == 0) {
                        q.push({curr.c,i,1});
                    }
                }
            }
        }
    }
    if(calls == 2 * N * N) return 0;
    else return -1;
}

int nextMove(int R) {
    return curr = nxt[curr][R];
}

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