Submission #233912

#	Time	Username	Problem	Language	Result	Execution time	Memory
233912		parsa_mobed	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	586 ms	7820 KiB

coprobber

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

using namespace std;
#define pii pair <int , int>
#define F first
#define S second
#define num(i, j) i * n + j
int deg[MAX_N], Win[MAX_N][MAX_N][2], Cnt[MAX_N][MAX_N], Par[MAX_N][MAX_N], curPos;

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]) deg[i]++;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) Cnt[i][j] = deg[j];
    queue <pii> q;
    for (int i = 0; i < n; i++) for (int t = 0; t < 2; t++) q.push({num(i, i), t}), Win[i][i][t] = 1, Par[i][i] = i;
    while (!q.empty()) {
        pii p = q.front(); q.pop();
        int cop = p.F / n, rob = p.F % n;
        if (p.S == 0) {
            // Robber turn
            for (int u = 0; u < n; u++)
                if ((u == cop || A[u][cop]) && !Win[u][rob][1])
                    Win[u][rob][1] = 1, Par[u][rob] = cop, q.push({num(u, rob), 1});
        } else {
            // Cop turn
            for (int u = 0; u < n; u++) if (A[u][rob]) {
                Cnt[cop][u]--;
                if (Cnt[cop][u] == 0 && !Win[cop][u][0]) Win[cop][u][0] = 1, q.push({num(cop, u), 0});
            }
        }
    }
    for (int i = 0; i < n; i++) {
        bool Can = 1;
        for (int j = 0; j < n; j++) Can &= Win[i][j][1];
        if (Can) return curPos = i;
    }
    return -1;
}

int nextMove(int robber) {
    return curPos = Par[curPos][robber];
}

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