oj.uz

답안 #24483

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
24483 2017-06-09T10:52:21 Z zoomswk 경찰관과 강도 (BOI14_coprobber) C++14
16 / 100
 430 ms 5940 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}});
            }
        }
        dp[1][i][i] = 0;
        for(int j=0; j<N; j++) if(A[i][j] || i == j){
            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(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.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 265 ms 5704 KB Output is correct
5 Correct 43 ms 2944 KB Output is correct
6 Correct 369 ms 5880 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 384 KB the situation repeated
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Incorrect 2 ms 384 KB the situation repeated
5 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 428 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 267 ms 5676 KB Output is correct
5 Correct 40 ms 2936 KB Output is correct
6 Correct 430 ms 5940 KB Output is correct
7 Incorrect 2 ms 384 KB the situation repeated
8 Halted 0 ms 0 KB -