Submission #233515

#	Time	Username	Problem	Language	Result	Execution time	Memory
233515		thecodingwizard	Cop and Robber (BOI14_coprobber)	C++11	100 / 100	579 ms	7184 KiB

coprobber

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

#include "coprobber.h"

#define ll long long
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, b) FOR(i, 0, b)
#define ii pair<int, int>
#define pA first
#define pB second

int n;
bool adj[500][500];
int ct[500][500];
int nextStep[500][500];
bool win[500][500];
int adjCt[500];
int curPos = 0;

int start(int N, bool A[MAX_N][MAX_N])
{
    n = N;
    F0R(i, n) {
        adjCt[i] = 0;
        F0R(j, n) {
            adj[i][j] = A[i][j];
            if (A[i][j]) adjCt[i]++;
            ct[i][j] = 0;
        }
    }

    queue<pair<int, ii>> q;
    F0R(i, n) {
        q.push({0,{i,i}});
        q.push({1,{i,i}});
        win[i][i] = true;
    }
    while (!q.empty()) {
        pair<int, ii> u = q.front(); q.pop();
        if (u.pA == 1) {
            // am robber
            F0R(i, n) {
                if (adj[i][u.pB.pA] || i==u.pB.pA) {
                    if (!win[i][u.pB.pB]) {
                        win[i][u.pB.pB] = true;
                        nextStep[i][u.pB.pB] = u.pB.pA;
                        q.push({0,{i,u.pB.pB}});
                    }
                }
            }
        } else {
            // am cop
            F0R(i, n) {
                if (adj[i][u.pB.pB]) {
                    ct[u.pB.pA][i]++;
                    if (ct[u.pB.pA][i] == adjCt[i]) {
                        q.push({1,{u.pB.pA,i}});
                    }
                }
            }
        }
    }
    F0R(i, n) {
        if (!win[0][i]) return -1;
    }

    return 0;
}

int nextMove(int R)
{
    return curPos = nextStep[curPos][R];
}

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