제출 #1053193

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1053193		Zbyszek99	경찰관과 강도 (BOI14_coprobber)	C++17	0 / 100	1 ms	2392 KiB

coprobber

#include <bits/stdc++.h>
#include "coprobber.h"
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define pii pair<int,int>
#define pb push_back
using namespace std;

struct dp
{
    int rob,police,move;
};

//   DP[police][robber][turn]
bool DP[MAX_N][MAX_N][2];
int zlicz[MAX_N][MAX_N][2];

vector<int> graf[MAX_N];
int n;
int cur_poz;

int start(int N, bool A[MAX_N][MAX_N])
{
    n = N;
    stack<dp> winning_pos;
    rep(i,0,n-1)
    {
        rep(j,0,n-1)
        {
            if(A[i][j] == 0)
            {
                graf[i].push_back(j);
            }
        }
    }
    rep(i,0,n-1)
    {
        rep(j,0,n-1)
        {
            for(auto& it: graf[j])
            {
                zlicz[i][j][1]++;
            }
            zlicz[i][j][0] = 0;
        }
    }
    rep(i,0,n-1)
    {
        winning_pos.push({i,i,0});
        winning_pos.push({i,i,1});
        zlicz[i][i][0] = 1;
        zlicz[i][i][1] = 0;
    }
    while(!winning_pos.empty())
    {
        dp t = winning_pos.top();
        winning_pos.pop();
        DP[t.police][t.rob][t.move] = 1;
        if(t.move == 0)
        {
            for(auto it: graf[t.police])
            {
                zlicz[it][t.rob][1]--;
                if(zlicz[it][t.rob][1] == 0)
                {
                    winning_pos.push({t.rob,it,1});
                }
            }
            zlicz[t.police][t.rob][1]--;
            if(zlicz[t.police][t.rob][1] == 0)
            {
                winning_pos.push({t.rob,t.police,1});
            }    
        }
        if(t.move == 1)
        {
            for(auto it: graf[t.rob])
            {
                zlicz[t.police][it][0]++;
                if(zlicz[it][t.rob][1] == 1)
                {
                    winning_pos.push({it,t.police,1});
                }
            }
        }
    }
    rep(start,0,n-1)
    {
        bool is = true;
        rep(end,0,n-1)
        {
            if(DP[start][end][0] == false) is = false;
        }
        if(is)
        {
            cur_poz = start;
            return start;
        } 
    }
    return -1;    
}

int nextMove(int R)
{
    for(auto it: graf[cur_poz])
    {
        if(DP[it][R][1]) return it;
    }    
}

컴파일 시 표준 에러 (stderr) 메시지

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:39:23: warning: unused variable 'it' [-Wunused-variable]
   39 |             for(auto& it: graf[j])
      |                       ^~
coprobber.cpp: In function 'int nextMove(int)':
coprobber.cpp:108:1: warning: control reaches end of non-void function [-Wreturn-type]
  108 | }
      | ^

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