Submission #1204029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204029		12345678	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	350 ms	9736 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=505;

enum Turn {COP, ROBBER};

int n, dp[nx][nx][2], deg[nx][nx], tmp[nx], cur, a[nx][nx], pa[nx][nx];
queue<tuple<int, int, Turn>> q;

int start(int N, bool A[MAX_N][MAX_N])
{
    n=N;
    for (int i=0; i<N; i++) for (int j=0;j <N; j++) a[i][j]=A[i][j];
    for (int i=0; i<N; i++) for (int j=0; j<N; j++) if (A[i][j]) tmp[i]++;
    for (int i=0; i<N; i++) for (int j=0; j<N;j ++) deg[i][j]=tmp[j];
    for (int i=0; i<N; i++) q.push({i, i, Turn::ROBBER}), dp[i][i][Turn::ROBBER]=1;
    while (!q.empty())
    {
        auto [cop, robber, turn]=q.front();
        q.pop();
        if (turn==COP)
        {
            for (int i=0; i<N; i++)
            {
                if (A[robber][i]) deg[cop][i]--;
                if (deg[cop][i]==0&&!dp[cop][i][Turn::ROBBER])
                {
                    dp[cop][i][Turn::ROBBER]=1;
                    q.push({cop, i, Turn::ROBBER});
                }
            }
        }
        else
        {
            for (int i=0; i<N; i++)
            {
                if ((A[cop][i]||cop==i)&&!dp[i][robber][Turn::COP])
                {
                    dp[i][robber][Turn::COP]=1;
                    pa[i][robber]=cop;
                    q.push({i, robber, Turn::COP});
                }
            }
        }
    }
    for (int i=0; i<N; i++)
    {
        int f=1;
        for (int j=0; j<N; j++) if (!dp[i][j][Turn::COP]) f=0;
        if (f) return cur=i;
    }
    return -1;
}

int nextMove(int R)
{
    return cur=pa[cur][R];
}

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