Submission #988312

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

coprobber

#include "coprobber.h"
#include<bits/stdc++.h>
using namespace std;
int dp[505][505][2];
int go[505][505];
int moves[505][505];
int vis[505][505][2];
vector<int>adj[505];
struct state{
    int cop,robber,turn;
    state(int _cop,int _robber,int _turn){
        cop=_cop,robber=_robber,turn=_turn;
    }
};
int cop;
int start(int N, bool A[MAX_N][MAX_N])
{
    for(int i=0;i<N;i++)for(int j=0;j<N;j++)if(A[i][j])adj[i].push_back(j);
    for(int i=0;i<N;i++)for(int j=0;j<N;j++)moves[i][j]+=adj[i].size();
    queue<state>q;
    for(int i=0;i<N;i++)q.push(state(i,i,0)),q.push(state(i,i,1)),vis[i][i][0]=vis[i][i][1]=1;
    while(!q.empty()){
        auto x=q.front();
        q.pop();
        dp[x.cop][x.robber][x.turn]=1;
        if(x.turn){
            for(auto temp:adj[x.cop]){
                if(vis[x.cop][temp][0])continue;
                moves[x.cop][temp]--;
                if(!moves[x.cop][temp])vis[x.cop][temp][0]=1,q.push(state(x.cop,temp,0));
            }
        }else{
            for(auto temp:adj[x.robber]){
                if(vis[temp][x.robber][1])continue;
                vis[temp][x.robber][1]=1;
                go[temp][x.robber]=x.cop;
                q.push(state(temp,x.robber,1));
            }
        }
    }
    for(int i=0;i<N;i++){
        int count=0;
        for(int j=0;j<N;j++)if(dp[i][j][1])count++;else break;
        if(count==N)return cop=i;
    }
    return -1;
}

int nextMove(int R)
{
    return cop=go[cop][R];
}

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