Submission #677489

#	Time	Username	Problem	Language	Result	Execution time	Memory
677489		dooompy	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	668 ms	10512 KiB

coprobber

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


using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

struct state {
    int cop, robber, move;
};

vector<int> adj[505];
int dp[505][505][2];
int moves[505][505][2]; // 0 - cops turn, 1 - robbers turn
int ct[505][505];

int pos = 0;

int start(int n, bool a[500][500]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j]) {
                adj[i].push_back(j);
            }
        }
    }

    queue<state> states;

    for (int i = 0; i < n; i++) {
        states.push({i, i, 0});
        states.push({i, i, 1});

        dp[i][i][0] = dp[i][i][1] = true;
        moves[i][i][0] = moves[i][i][1] = i;
    }

    while (!states.empty()) {
        auto [cop, robber, move] = states.front(); states.pop();

        if (move == 0) {
            // robber just moved to this square

            for (auto nxt : adj[robber]) {
                ct[cop][nxt]++;

                if (ct[cop][nxt] == adj[nxt].size()) {
                    // forced to move
                    dp[cop][nxt][1] = 1;
                    states.push({cop, nxt, 1});
                }
            }
        } else {
            for (auto nxt : adj[cop]) {
                if (dp[nxt][robber][0] == 1) continue;
                dp[nxt][robber][0] = 1;
                moves[nxt][robber][0] = cop;
                states.push({nxt, robber, 0});
            }

            if (dp[cop][robber][0] != 1) {
                dp[cop][robber][0] = 1;
                moves[cop][robber][0] = cop;
                states.push({cop, robber, 0});
            }
        }
    }

    int ok = 0;
    for (int i = 0; i < n; i++) {
        if (dp[0][i][0] != 1) {
            ok = -1;
            break;
        }
    }

    return ok;
}

int nextMove(int r) {
    return pos = moves[pos][r][0];
}
 

Compilation message (stderr)

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:73:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |                 if (ct[cop][nxt] == adj[nxt].size()) {
      |                     ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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