Submission #17353

#	Time	Username	Problem	Language	Result	Execution time	Memory
17353		eaststar	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	834 ms	7744 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});
            }
        }
    }
    for(i=0;i<N;++i){
        for(j=0;j<N;++j)if(a[i][j][0])break;
        if(j==N)return p=i;
    }
    return -1;
}
int nextMove(int R){
    return p=nx[p][R];
}

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