Submission #1072505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072505		ortsac	Cop and Robber (BOI14_coprobber)	C++17	0 / 100	1 ms	2392 KiB

coprobber

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

using namespace std;

struct Po {
    int c, r, t;
};

Po getPo(int i, int j, int k) {
    Po ans;
    ans.c = i;
    ans.r = j;
    ans.t = k;
    return ans;
}

bool adj[MAX_N][MAX_N];
bool dp[MAX_N][MAX_N][2];
bool vis[MAX_N][MAX_N][2];
int rem[MAX_N][MAX_N];
// rem[i][j][0] = how many do I need to remove from position (i, j) to be able to add it
// (i, j, 0) needs to have all zeroes
// (i, j, 1) needs to have all ones
int n;
int atual;

int start(int N, bool A[MAX_N][MAX_N]) {
    #pragma region Set values
    n = N;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            adj[i][j] = A[i][j];
            dp[i][j][1] = 1;
            for (int k = 0; k < n; k++) {
                rem[k][i]++;
            }
        }
    }
    #pragma endregion
    queue<Po> process;
    for (int i = 0; i < n; i++) {
        dp[i][i][0] = dp[i][i][1] = 1;
        vis[i][i][0] = vis[i][i][1] = 1;
        process.push(getPo(i, i, 0));
        process.push(getPo(i, i, 1));
    }
    while (!process.empty()) {
        auto u = process.front();
        process.pop();
        if (u.t) {
            // robbers turn
            if (!dp[u.c][u.r][1]) continue; // is 0
            for (int i = 0; i < n; i++) {
                if (!adj[u.c][i] || vis[i][u.r][0]) continue;
                dp[i][u.r][0] = 1;
                vis[i][u.r][0] = 1;
                process.push(getPo(i, u.r, 0));
            }
        } else {
            // cops turn
            if (dp[u.c][u.r][0]) continue; // is 1
            for (int i = 0; i < n; i++) {
                if (!adj[u.r][i] || vis[u.c][i][1]) continue;
                rem[u.c][i]--;
                if (rem[u.c][i] == 0) {
                    dp[u.c][i][1] = 0;
                    vis[u.c][i][1] = 1;
                    process.push(getPo(u.c, i, 1));
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        bool ok = 1;
        for (int j = 0; j < n; j++) ok = (ok && dp[i][j][0]);
        if (ok) {
            return (atual = i);
        }
    }
    return -1;
}

int nextMove(int R) {
    for (int i = 0; i < n; i++) {
        if (!adj[atual][i]) continue;
        if (dp[i][R][0]) return (atual = i);
    }
}

Compilation message (stderr)

coprobber.cpp:29: warning: ignoring '#pragma region Set' [-Wunknown-pragmas]
   29 |     #pragma region Set values
      | 
coprobber.cpp:40: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   40 |     #pragma endregion
      | 
coprobber.cpp: In function 'int nextMove(int)':
coprobber.cpp:89:1: warning: control reaches end of non-void function [-Wreturn-type]
   89 | }
      | ^

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