Submission #1072593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072593		ortsac	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	441 ms	10064 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][2];
int order[MAX_N][MAX_N][2];
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];
            if (adj[i][j]) {
                for (int k = 0; k < n; k++) {
                    rem[k][i][1]++;
                    rem[i][k][0]++;
                }
            }
        }
    }
    #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));
    }
    int curr = 0;
    while (!process.empty()) {
        auto u = process.front();
        process.pop();
        //cout << u.c << " " << u.r << " " << u.t << " is: " << dp[u.c][u.r][u.t] << "\n";
        order[u.c][u.r][u.t] = ++curr;
        if (u.t) {
            // robbers turn
            for (int i = 0; i < n; i++) {
                if ((!adj[u.c][i] && (i != u.c)) || vis[i][u.r][0]) continue;
                if (dp[u.c][u.r][1]) {
                    dp[i][u.r][0] = 1;
                    vis[i][u.r][0] = 1;
                    process.push(getPo(i, u.r, 0));
                } else {
                    rem[i][u.r][0]--;
                    if (rem[i][u.r][0] == 0) {
                        dp[i][u.r][0] = 0;
                        vis[i][u.r][0] = 1;
                        process.push(getPo(i, u.r, 0));
                    } 
                }
            }
        } else {
            // cops turn
            for (int i = 0; i < n; i++) {
                if (!adj[u.r][i] || vis[u.c][i][1]) continue;
                if (dp[u.c][u.r][0]) {
                    rem[u.c][i][1]--;
                    if (rem[u.c][i][1] == 0) {
                        dp[u.c][i][1] = 1;
                        vis[u.c][i][1] = 1;
                        process.push(getPo(u.c, i, 1));
                    }
                } else {
                    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] && (i != atual)) continue;
        if (dp[i][R][1] && (order[i][R][1] < order[atual][R][0])) return (atual = i);
    }
    return -1;
}

Compilation message (stderr)

coprobber.cpp:27: warning: ignoring '#pragma region Set' [-Wunknown-pragmas]
   27 |     #pragma region Set values
      | 
coprobber.cpp:40: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   40 |     #pragma endregion
      |

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