Submission #233905

#	Time	Username	Problem	Language	Result	Execution time	Memory
233905		parsa_mobed	Cop and Robber (BOI14_coprobber)	C++14	16 / 100	273 ms	4892 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], 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++) deg[i] += A[i][j];
    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}), Par[i][i] = i, Win[i][i] = 1;
    while (!q.empty()) {
        pii p = q.front(); q.pop();
        int cop = p.F / n, rob = p.F % n;
        if (p.S == 0) {
            // Rober turn
            for (int u = 0; u < n; u++)
                if (A[u][cop] && !Win[u][rob])
                    Win[u][rob] = 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) 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];
        if (Can) return curPos;
    }
    return -1;
}

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

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