Submission #84691

#	Time	Username	Problem	Language	Result	Execution time	Memory
84691		teomrn	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	348 ms	5292 KiB

coprobber

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

using namespace std;

const int NMAX = 510;
vector <int> adia[NMAX + 10];
bool dp[NMAX + 10][NMAX + 10][2];
int to[NMAX + 10][NMAX + 10];
int liber[NMAX + 10][NMAX + 10];

void open(int x, int y, int who)
{
    dp[x][y][who] = 1;
    if (who == 1) {
        /// muta politistul
        for (auto i : adia[x]) {
            if (!dp[i][y][0]) {
                to[i][y] = x;
                open(i, y, 0);
            }
        }
        if (!dp[x][y][0]) {
            to[x][y] = x;
            open(x, y, 0);
        }
    }
    else {
        /// hotul muta
        for (auto i : adia[y]) {
            liber[x][i]--;
            if (!liber[x][i] && !dp[x][i][1])
                open(x, i, 1);
        }
    }
}

int act;

int start(int N, bool A[MAX_N][MAX_N])
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (A[i][j])
                adia[i].push_back(j);

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            liber[i][j] = adia[j].size();

    for (int i = 0; i < N; i++) {
        if (!dp[i][i][0])
            open(i, i , 0);
        if (!dp[i][i][1])
            open(i, i, 1);
    }

    for (act = 0; act < N; act++) {
        bool ok = 1;
        for (int i = 0; i < N; i++)
            if (!dp[act][i][0])
                ok = 0;
        if (ok)
            return act;
    }
    return -1;
}

int nextMove(int R)
{
    act = to[act][R];
    return act;
}

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