Submission #1140930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140930		dpsaveslives	Cop and Robber (BOI14_coprobber)	C++20	100 / 100	288 ms	9716 KiB

coprobber

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500;
int zug[500][500],cnt[500][500],win[2][500][500];
int curpos = 0;
vector<int> adj[MAXN];
//bool inp[MAXN][MAXN];
int start(int N, bool A[MAXN][MAXN]){
    for(int i = 0;i<N;++i){
        for(int j = 0;j<N;++j){
            if(A[i][j]){
                adj[i].push_back(j);
            }
        }
    }
    queue<array<int,3>> q;
    for(int i = 0;i<N;++i){
        win[0][i][i] = win[1][i][i] = 1;
        q.push({0,i,i}); q.push({1,i,i});
        zug[i][i] = i;
    }
    while(!q.empty()){
        array<int,3> state = q.front(); q.pop();
        int tp = state[0], P = state[1], R = state[2];
        if(tp == 0){
            for(auto v : adj[R]){
                if(win[1][P][v]) continue;
                ++cnt[P][v];
                if(cnt[P][v] == adj[v].size()){
                    win[1][P][v] = 1;
                    q.push({1,P,v});
                }
            }
        }
        else{
            adj[P].push_back(P);
            for(auto v : adj[P]){
                if(win[0][v][R]) continue;
                win[0][v][R] = 1;
                q.push({0,v,R});
                zug[v][R] = P;
            }
            adj[P].pop_back();
        }
    }
    for(int i = 0;i<N;++i){
        bool good = true;
        for(int j = 0;j<N;++j){
            if(win[0][i][j] == 0){
                good = false;
                break;
            }
        }
        if(good){
            curpos = i;
            return curpos;
        }
    }
    return -1;
}
int nextMove(int R){
    curpos = zug[curpos][R];
    return curpos;
}

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