Submission #160388

#	Time	Username	Problem	Language	Result	Execution time	Memory
160388		PeppaPig	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	1281 ms	8184 KiB

coprobber

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

#define iii tuple<int, int, int>

using namespace std;

const int N = 505;

int n, ret;
int par[N][N], cnt[N][N], adj[N]; //0 - cop turn, 1 - robber turn
bool chk[2][N][N];
queue<iii> Q;

int start(int _n, bool A[MAX_N][MAX_N]) {
    n = _n;
    memset(par, -1, sizeof par);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) adj[i] += A[i][j];
        Q.emplace(0, i, i), Q.emplace(1, i, i);
        chk[0][i][i] = chk[1][i][i] = true;
    }
    while(!Q.empty()) {
        iii now = Q.front(); Q.pop();
        int T, cop, rob;
        tie(T, cop, rob) = now;

        if(T == 0) {
            for(int i = 0; i < n; i++) if(A[rob][i] && !chk[1][cop][i]) {
                ++cnt[cop][i];
                if(cnt[cop][i] == adj[i]) {
                    chk[1][cop][i] = true;
                    Q.emplace(1, cop, i);
                }
            }
        } else {
            for(int i = 0; i < n; i++) if((A[cop][i] || i == cop) && !chk[0][i][rob]) {
                chk[0][i][rob] = true;
                par[i][rob] = cop;
                Q.emplace(0, i, rob);
            }
        }
    }
    for(int i = 0; i < n; i++) {
        bool valid = true;
        for(int j = 0; j < n; j++) if(i != j && par[i][j] == -1) valid = false;
        if(valid) return ret = i;
    }
    return -1;
}

int nextMove(int R) {
    return ret = par[ret][R];
}

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