Submission #417800

#	Time	Username	Problem	Language	Result	Execution time	Memory
417800		KULIKOLD	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	1006 ms	9352 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const int DIM = 507;
int dp[2][DIM][DIM];
bool valid[2][DIM][DIM];
struct node{
    ll turn,a,b;
};
int POS,N;
bool mas[MAX_N][MAX_N];
int depth[2][DIM][DIM];
int start(int N, bool A[MAX_N][MAX_N])
{
    ::N = N;
    queue<node> Q;
    for(int i = 0;i<N;++i){
        dp[0][i][i] = 1;
        dp[1][i][i] = N;
        valid[0][i][i] = valid[1][i][i] = 1;
        Q.push({0,i,i});
        Q.push({1,i,i});
    }
    for(int i = 0;i<N;++i)
        for(int j = 0;j<N;++j)
            mas[i][j] = A[i][j];
    for(ll i = 0;i<N;++i){
        for(ll k = 0;k<N;++k)
            for(ll j = 0;j<N;++j){
                if (!A[k][j]){
                    dp[1][i][k]++;
                    if (dp[1][i][k]==N){
                        valid[1][i][k] = 1;
                        Q.push({1,i,k});
                    }
                }
            }
    }
    while(!Q.empty()){
        node pos = Q.front();
        Q.pop();
        if (pos.turn==0){
            for(ll b = 0;b<N;++b){
                if (!A[pos.b][b])
                    continue;
                ++dp[1][pos.a][b];
                if (dp[1][pos.a][b]==N)
                    Q.push({1,pos.a,b}),valid[1][pos.a][b] = 1,depth[1][pos.a][b] = depth[0][pos.a][pos.b]+1;

            }
        }
        else{
            for(ll a = 0;a<N;++a){
                if (!dp[0][a][pos.b] && (A[pos.a][a] || pos.a==a)){
                    dp[0][a][pos.b] = 1;
                    valid[0][a][pos.b] = 1;
                    Q.push({0,a,pos.b}), valid[0][a][pos.b] = 1, depth[0][a][pos.b] = depth[1][pos.a][pos.b]+1;
                }
            }
        }
    }
    for(ll i = 0;i<N;++i){
        ll flag = 0;
        for(ll j = 0;j<N;++j){
            if (!valid[0][i][j]){
                flag = 1;
                break;
            }
        }
        if (!flag){
            POS = i;
            return i;
        }
    }
    return -1;
}

int nextMove(int R)
{
    int nxt = -1;
    for(ll a = 0;a<N;++a){
        if (valid[1][a][R] && (mas[POS][a] || a==POS)){
            if (nxt==-1)
                nxt = a;
            else if (depth[1][nxt][R]>depth[1][a][R])
                nxt = a;
        }
    }

    POS = nxt;
    return nxt;
}

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