Submission #1213938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213938		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(); // police,robber, turn  
        q.pop();
        if (vis[p][r][t] == 2) continue; // already done
        vis[p][r][t] = 2;
        if (t == 0) { // robber's turn
            for (int u : adj[r]) {
                cnt[p][u]++; 
                if (cnt[p][u] == adj[u].size()) {
                    if (vis[p][u][!t] == 0) {
                        q.push({p,u,!t});
                        vis[p][u][!t] = 1;
                    }
                }
            }
        }else {
            for (int u : adj[p]) {
                if (vis[u][r][!t] == 0) {
                    q.push({u,r,!t});
                    nxt[p][r] = u;
                    vis[u][r][!t] = 1;
                }
                // if police chooses stay 
                if (vis[p][r][!t] == 0) {
                    q.push({p,r,!t});
                    nxt[p][r] = p;
                    vis[p][r][!t] = 1;
                }
            }
        }
    }
    for (int i = 0; i < N;i++) {
        bool ok = 1;
        for (int j = 0; j < N;j++) {
            if (vis[i][j][1] != 2) ok = 0;
        }
        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