Submission #145795

#	Time	Username	Problem	Language	Result	Execution time	Memory
145795		letrongdat	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	861 ms	9588 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>
const int maxN = 500;
using namespace std;
#define forn(i, a, b)   for(int i=a; i<=b; ++i)
#define repn(i, a, b)   for(int i=a; i <b; ++i)

int cur;
int mov[maxN][maxN], deg[maxN][maxN];
int W[maxN][maxN][2];
int start(int N, bool A[maxN][maxN]) {
    queue < tuple < int, int, int > > q;
    repn(i, 0, N) repn(j, 0, N) repn(k, 0, N) deg[i][j] += A[j][k];
    repn(i, 0, N) forn(turn, 0, 1) {
        W[i][i][turn] = 1;
        q.push({i, i, turn});
    }
    while (q.size()) {
        int c, r, t;
        tie(c, r, t) = q.front();
        q.pop();
        repn(i, 0, N) {
            if (t) {
                if ( (A[c][i] || i == c) && !W[i][r][0]) {
                    mov[i][r] = c;
                    W[i][r][0] = true;
                    q.push({i, r, 0});
                }
                continue;
            }
            if (A[r][i] && !W[c][i][1] && --deg[c][i] < 1) {
                W[c][i][1] = true;
                q.push({c, i, 1});
            }
        }
    }
    repn(i, 0 ,N) {
        int ok = 1;
        repn(j, 0, N) ok &= W[i][j][0];
        if (ok) return cur = i;
    }
    return -1;
}
int nextMove(int R) {
    return cur = mov[cur][R];
}

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