oj.uz

Submission #24475

# Submission time Handle Problem Language Result Execution time Memory
24475 2017-06-09T10:33:31 Z zoomswk Cop and Robber (BOI14_coprobber) C++14
0 / 100
 1500 ms 384 KB 
#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];
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[0][i][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}});
            }
        }
    }
    while(!q.empty()){
        int st = q.front().first;
        int pol = q.front().second.first, thief = q.front().second.second;
        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]){
                        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][i][thief]++;
                    if(cnt[1][i][thief] == adj[i]){
                        q.push({1, {i, thief}});
                    }
                }
            }
        }
    }
    for(int i=0; i<N; i++){
        int ok = 0;
        for(int j=0; j<N; j++){
            if(cnt[0][i][j]) ok++;
        }
        if(ok == N){
            pos = i;
            return i;
        }
    }
    return -1;
}

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

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1585 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Cop can catch the robber, but start() returned -1
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1577 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1570 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -