Submission #1076222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076222		anton	Cop and Robber (BOI14_coprobber)	C++17	60 / 100	2391 ms	8528 KiB

coprobber

#include "coprobber.h"
#include<bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define P complex<int>

vector<vector<int>> adj;
bool B[MAX_N][MAX_N];
int N;


int rem[MAX_N][MAX_N];
int next_pos[MAX_N][MAX_N];
bool is_vis[2][MAX_N][MAX_N];

struct Pos{
    int player_id;
    int cop_pos, r_pos;
    Pos(){};
    Pos(int _id, int _cop_pos, int _r_pos){
        player_id = _id;
        cop_pos = _cop_pos;
        r_pos = _r_pos;
    }

    vector<Pos> rev_adj(){
        vector<Pos> res;
        if(player_id == 0){
            for(auto e: adj[r_pos]){
                res.push_back(Pos(1, cop_pos, e));
            }
        }
        if(player_id == 1){
            for(auto e: adj[cop_pos]){
                res.push_back(Pos(0, e, r_pos));
            }
            res.push_back(Pos(0, cop_pos, r_pos));
        }
        return res;
    }
    bool& vis(){
        return is_vis[player_id][cop_pos][r_pos];
    }
};

int cop_pos = 0; 
int start(int _N, bool A[MAX_N][MAX_N])
{
    N= _N;
    adj.resize(N);
    for(int i = 0; i<MAX_N; i++){
        for(int j = 0; j<MAX_N; j++){
            B[i][j] = A[i][j];
            if(B[i][j]){
                adj[i].push_back(j);
            }
        }
    }

    for(int i = 0; i<N; i++){
        for(int j= 0; j<N; j++){
            rem[i][j] = adj[j].size();
        }
    }

    queue<Pos> wining;
    for(int i = 0; i<N; i++){
        wining.push(Pos(0, i, i));
        wining.push(Pos(1, i, i));
    }

    while(wining.size()>0){
        Pos cur = wining.front();
        cur.vis() = true;
        wining.pop();
        if(cur.player_id == 1){
            for(auto e: cur.rev_adj()){
                if(!e.vis()){
                    e.vis() = true;
                    next_pos[e.cop_pos][e.r_pos] = cur.cop_pos;
                    wining.push(e);
                }
            }
        }
        else{
            for(auto e: cur.rev_adj()){
                rem[e.cop_pos][e.r_pos]--;
                if(rem[e.cop_pos][e.r_pos] == 0){
                    e.vis() = true;
                    wining.push(e);
                }
            }
        }
    }

    for(int i = 0; i<N; i++){
        bool ok = true;
        for(int j  = 0; j<N; j++){
            if(!is_vis[0][i][j]){
                ok = false;
            }
        }

        if(ok){
            cop_pos = i;
            return i;
        }
    }

    return -1;
}
int nextMove(int R)
{
    cop_pos = next_pos[cop_pos][R];
    return cop_pos;
}

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