Submission #1076324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076324		anton	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	301 ms	5456 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;
    }
    bool& vis(){
        return is_vis[player_id][cop_pos][r_pos];
    }
};

int cop_pos = 0; 

void calc(Pos cur){
    if(cur.vis()){
        return;
    }
    cur.vis() = true;
    if(cur.player_id == 1){
        for(auto s: adj[cur.cop_pos]){
            auto e =Pos(0, s, cur.r_pos);
            if(!e.vis()){
                next_pos[e.cop_pos][e.r_pos] = cur.cop_pos;
                calc(e);
            }
        }
        auto e =Pos(0, cur.cop_pos, cur.r_pos);
        if(!e.vis()){
            next_pos[e.cop_pos][e.r_pos] = cur.cop_pos;
            calc(e);
        }
    }
    else{
        for(auto s: adj[cur.r_pos]){
            auto e =Pos(1, cur.cop_pos, s);
            if(!e.vis()){
                rem[e.cop_pos][e.r_pos]--;
                if(rem[e.cop_pos][e.r_pos] == 0){
                    calc(e);
                }
            }
        }
        
    }
}


int start(int _N, bool A[MAX_N][MAX_N])
{
    N= _N;
    adj.resize(N);
    for(int i = 0; i<N; i++){
        for(int j = 0; j<N; j++){
            is_vis[0][i][j] = false;
            is_vis[1][i][j] = false;
            if(A[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();
        }
    }

    for(int i = 0; i<N; i++){  
        calc(Pos(0, i, i));
        calc(Pos(1, i, i));
    }

    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: 40 / 40