Submission #1165137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165137		spycoderyt	Cop and Robber (BOI14_coprobber)	C++20	100 / 100	478 ms	11536 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
int as[MAX_N][MAX_N],w[MAX_N][MAX_N][2],f[MAX_N][MAX_N];
int qh,qt;
array<int,3> qu[MAX_N*MAX_N*2];
int p=0;
int start(int n, bool a[MAX_N][MAX_N])
{
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++) {
            for(int k = 0;k<n;k++) as[k][i] += a[i][j];
        }
    }
    qh=qt=0;
    for(int i = 0;i<n;i++) {
        for(int j = 0;j<2;j++) {
            w[i][i][j]=1;
            qu[qt++]={i,i,j};
        }
    }
    while(qh<qt){
        array<int,3> u = qu[qh++];
        for(int i = 0;i<n;i++) {
            if(u[2]&&(a[i][u[0]]||i==u[0])&&!w[i][u[1]][0]){
                w[i][u[1]][0]=1;
                qu[qt++]={i,u[1],0};
                f[i][u[1]]=u[0];
            } else if(!u[2]&&a[i][u[1]]&&!w[u[0]][i][1]&&--as[u[0]][i]<=0){
                w[u[0]][i][1]=1;
                qu[qt++]={u[0],i,1};
            }
        }
    }
    int ok = 1;
    for(int i = 0;i<n&&ok;i++){
        ok=w[0][i][0];
    }
    return ok?0:-1;
}

int nextMove(int R)
{
    return p=f[p][R];
}

/*
/usr/bin/g++ -DEVAL -std=gnu++11 -O2 -pipe -s -o askask grader.cpp askask2.cpp

/usr/bin/g++ -DEVAL -std=gnu++11 -O2 -pipe -s -o coprobber grader.cpp coprobber.cpp
*/

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