Submission #1214088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214088		i_love_spring	Cop and Robber (BOI14_coprobber)	C++20	100 / 100	323 ms	9820 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 = 0;
int start(int N, bool A[MAX_N][MAX_N])
{
    for (int i = 0; i < N;i++) {
        for (int j = i + 1; j < N;j++) {
            if (A[i][j]) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }
    memset(cnt,0,sizeof(cnt));
    memset(vis,0,sizeof(vis));
    memset(nxt,0,sizeof(nxt));
    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][1] == 0) {
                        q.push({p,u,1});
                        vis[p][u][1] = 1;
                    }
                }
            }
        }else {
            for (int u : adj[p]) {
                if (vis[u][r][0] == 0) {
                    q.push({u,r,0});
                    nxt[u][r] = p;
                    vis[u][r][0] = 1;
                }
            }
            // if police chooses stay 
            if (vis[p][r][0] == 0) {
                q.push({p,r,0});
                nxt[p][r] = p;
                vis[p][r][0] = 1;
            }
        }
    }
    for (int i = 0; i < N;i++) {
        bool ok = 1;
        for (int j = 0; j < N;j++) {
            if (vis[i][j][1] == 0) ok = 0;
        }
        if (ok) {
            cur = i;
            return i;
        }
    }

    return  -1;
}

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

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