제출 #24483

#제출 시각아이디문제언어결과실행 시간메모리
24483zoomswk경찰관과 강도 (BOI14_coprobber)C++14
16 / 100
430 ms5940 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...