Submission #25368

#	Time	Username	Problem	Language	Result	Execution time	Memory
25368		minimario	Cop and Robber (BOI14_coprobber)	C++14	0 / 100	2 ms	384 KiB

coprobber

#include "coprobber.h"
#include <queue>
using namespace std;
struct data{
    int x,y,z;
}t;
queue<data> q;
int a[510][510][2],nx[510][510],p;
int start(int N, bool A[MAX_N][MAX_N]){
    int i,j,cnt;
    for(i=0;i<N;++i){
        cnt=0;
        for(j=0;j<N;++j)if(A[i][j])++cnt;
        for(j=0;j<N;++j)if(i!=j)a[j][i][0]=1,a[j][i][1]=cnt;
        q.push({i,i,0}),q.push({i,i,1});
    }
    while(!q.empty()){
        t=q.front();
        q.pop();
        if(t.z){
            for(i=0;i<N;++i)if((t.x==i||A[t.x][i])&&a[i][t.y][0]){
                --a[i][t.y][0];
                if(!a[i][t.y][0])q.push({i,t.y,0}),nx[i][t.y]=t.x;
            }
        }
        else{
            for(i=0;i<N;++i)if(A[t.y][i]&&a[t.x][i][1]){
                --a[t.x][i][1];
                if(!a[t.x][i][1])q.push({t.x,i,1});
            }
        }
    }
  	int toret = -1;
    for(i=0;i<N;++i){
        for(j=0;j<N;++j)if(a[i][j][0])break;
        if(j==N) { p = i; toret = p; break; }
    }
    int ct = 0;
    for(i=0; i<N; ++i) {
      for (j=0; j<N; ++j) {
        for (int k=0; k<2; ++k) {
          if (a[i][j][k] == 1) { ct++; }
        }      
      }
    }
    if (ct == 2*N*N) { return toret; }
    return -1;
}
int nextMove(int R){
    return p=nx[p][R];
}

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