Submission #763050

#	Time	Username	Problem	Language	Result	Execution time	Memory
763050		vjudge1	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	295 ms	6640 KiB

coprobber

#include "coprobber.h"
#include<vector>
#pragma GCC optimize(2)
int ok[MAX_N][MAX_N][2], move[MAX_N][MAX_N], vis[MAX_N][MAX_N][2], sz[MAX_N][MAX_N];
bool a[MAX_N][MAX_N];
std::vector<int> adj[MAX_N];
int pos;
void dfs(int x, int y, int who)
{
    ok[x][y][who] = 1;
    if (who == 1) {
        for (auto i : adj[x]) {
            if (!ok[i][y][0]) {
                move[i][y] = x;
                dfs(i, y, 0);
            }
        }
        if (!ok[x][y][0]) {
            move[x][y] = x;
            dfs(x, y, 0);
        }
    }
    else {
        for (auto i : adj[y]) {
            sz[x][i]--;
            if (!sz[x][i] && !ok[x][i][1])
                dfs(x, i, 1);
        }
    }
}
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])
                adj[i].push_back(j);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            sz[i][j] = adj[j].size();
    for (int i = 0; i < N; i++) {
        if (!ok[i][i][0])
            dfs(i, i , 0);
        if (!ok[i][i][1])
            dfs(i, i, 1);
    }
    for (pos = 0; pos < N; pos++) {
        bool still = 1;
        for (int i = 0; i < N; i++)
            if (!ok[pos][i][0])
                still = 0;
        if (still)
            return pos;
    }
    return -1;
}

int nextMove(int R)
{
    return pos=move[pos][R];
}

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