Submission #24491

#	Time	Username	Problem	Language	Result	Execution time	Memory
24491		zoomswk	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	582 ms	9676 KiB

coprobber

#include <stdio.h>
#include <queue>
#include "coprobber.h"
using namespace std;

int dp[2][500][500]; //dp[police=0, thief=1][police][thief]
int cnt[2][500][500];
int adj[500];
int vs[2][500][500];
queue<pair<int, pair<int, int>>> q;
int pos;

int start(int N, bool A[MAX_N][MAX_N]){
    for(int i=0; i<N; i++) for(int j=0; j<N; j++) dp[0][i][j] = -1, dp[1][i][j] = -1;
    for(int i=0; i<N; i++) for(int j=0; j<N; j++) if(A[i][j]) adj[i]++;
    for(int i=0; i<N; i++){
        dp[1][i][i] = -1;
        q.push({1, {i, i}});
        /*
        for(int j=0; j<N; j++) if(A[i][j]){
            cnt[1][i][j]++;
            if(cnt[1][i][j] == adj[j]){
                q.push({1, {i, j}});
            }
        }
        dp[1][i][i] = -1;
        for(int j=0; j<N; j++) if(A[i][j] || i == j){
            dp[0][j][i] = i;
            q.push({0, {j, i}});
        }
         */
    }
    while(!q.empty()){
        int st = q.front().first;
        int pol = q.front().second.first, thief = q.front().second.second;
        q.pop();
        if(vs[st][pol][thief]) continue;
        vs[st][pol][thief] = 1;
        if(st){
            // thief's turn --> updating police's turns
            if(dp[st][pol][thief] == -1){
                // thief loses --> neighboring polices win
                for(int i=0; i<N; i++){
                    if(!A[i][pol] && i != pol) continue;
                    if(dp[0][i][thief] == -1){
                        dp[0][i][thief] = pol;
                        q.push({0, {i, thief}});
                    }
                }
            } else{
                // thief wins --> neighboring polices might lose
                for(int i=0; i<N; i++){
                    if(!A[i][pol] && i != pol) continue;
                    cnt[0][i][thief]++;
                    if(cnt[0][i][thief] == adj[i]+1){
                        q.push({0, {i, thief}});
                    }
                }
            }
        } else{
            // police's turn --> updating thief's turns
            if(dp[st][pol][thief] == -1){
                // police loses --> neighboring thieves win
                for(int i=0; i<N; i++){
                    if(!A[i][thief]) continue;
                    if(dp[1][pol][i] == -1){
                        dp[1][pol][i] = thief;
                        q.push({1, {pol, i}});
                    }
                }
            } else{
                // police wins --> neighboring thieves might lose
                for(int i=0; i<N; i++){
                    if(!A[i][thief]) continue;
                    cnt[1][pol][i]++;
                    if(cnt[1][pol][i] == adj[i]){
                        q.push({1, {pol, i}});
                    }
                }
            }
        }
    }
    for(int i=0; i<N; i++){
        int ok = 0;
        for(int j=0; j<N; j++){
            if(dp[0][i][j] != -1) ok++;
        }
        if(ok == N){
            pos = i;
            return i;
        }
    }
    return -1;
}

int nextMove(int R){
    pos = dp[0][pos][R];
    return pos;
}

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