Submission #1213945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213945		i_love_spring	Cop and Robber (BOI14_coprobber)	C++20	0 / 100	0 ms	328 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
const int nx = 505;
#define ar array
int nxt[nx][nx], cnt[nx][nx], vis[nx][nx][2];
vector<int> adj[nx];
queue<ar<int, 3>> q;
int cur;

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++) {
        q.push({i, i, 1});
        q.push({i, i, 0});
    }

    while (!q.empty()) {
        auto [p, r, t] = q.front();
        q.pop();
        if (vis[p][r][t] == 2) continue;
        vis[p][r][t] = 2;

        if (t == 0) { // Robber's turn
            for (int u : adj[r]) {
                cnt[p][u]++;
                if (cnt[p][u] == (int)adj[u].size() && vis[p][u][1] == 0) {
                    q.push({p, u, 1});
                    vis[p][u][1] = 1;
                }
            }
        } else { // Police's turn
            for (int u : adj[p]) {
                if (vis[u][r][0] == 0) {
                    q.push({u, r, 0});
                    vis[u][r][0] = 1;
                    nxt[p][r] = u;
                }
            }
            if (vis[p][r][0] == 0) {
                q.push({p, r, 0});
                vis[p][r][0] = 1;
                nxt[p][r] = p;
            }
        }
    }

    for (int i = 0; i < N; i++) {
        bool ok = true;
        for (int j = 0; j < N; j++)
            if (vis[i][j][1] == 0)
                ok = false;
        if (ok) {
            cur = i;
            return i;
        }
    }

    return -1;
}

int nextMove(int R) {
    return cur = nxt[cur][R];
}

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