Submission #492837

#	Time	Username	Problem	Language	Result	Execution time	Memory
492837		Rainbowbunny	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	1396 ms	9552 KiB

coprobber

#include <bits/stdc++.h>
using namespace std;

#define MAX_N 500

int cop;
int need[2][MAX_N][MAX_N], Next[MAX_N][MAX_N];
int dp[2][MAX_N][MAX_N];

int start(int N, bool Adj[MAX_N][MAX_N]) 
{
    for(int i = 0; i < N; i++)
    {
        int degree = 0;
        for(int j = 0; j < N; j++)
        {
            degree += Adj[i][j];
        }
        for(int j = 0; j < N; j++)
        {
            need[0][i][j] = 1;
            need[1][j][i] = degree;
            if(i == j)
            {
                need[0][i][i] = -1;
                need[1][i][i] = -1;
            }
        }
    }
    queue <tuple <int, int, int> > Q;
    for(int i = 0; i < N; i++)
    {
        Q.emplace(0, i, i);
        Q.emplace(1, i, i);
    }
    int cnt = 0;
    while(!Q.empty())
    {
        int p, u, v;
        tie(p, u, v) = Q.front();
        dp[p][u][v] = 1;
        cnt++;
        Q.pop();
        if(p == 0)
        {
            for(int i = 0; i < N; i++)
            {
                if(Adj[v][i])
                {
                    need[1][u][i]--;
                    if(need[1][u][i] == 0)
                    {
                        Q.emplace(1, u, i);
                    }
                }
            }
        }
        else
        {
            for(int i = 0; i < N; i++)
            {
                if(Adj[u][i] or i == u)
                {
                    need[0][i][v]--;
                    if(need[0][i][v] == 0)
                    {
                        Q.emplace(0, i, v);
                        Next[i][v] = u;
                    }
                }
            }
        }
    }
    if(cnt == 2 * N * N)
    {
        return 0;
    }
    else
    {
        return -1;
    }
}

int nextMove(int R) 
{
    return cop = Next[cop][R];
}

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