제출 #1076286

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1076286		anton	경찰관과 강도 (BOI14_coprobber)	C++17	60 / 100	2238 ms	17392 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];
    }
    bool operator<(const Pos b)const{
        if(player_id!=b.player_id){
            return player_id<b.player_id;
        }
        if(cop_pos != b.cop_pos){
            return cop_pos<b.cop_pos;
        }
        if(r_pos != b.r_pos){
            return r_pos < b.r_pos;
        }
        return false;
    }
};

int cop_pos = 0; 

void calc(Pos cur){
    if(cur.vis()){
        return;
    }
    cur.vis() = true;
    if(cur.player_id == 1){
        for(auto e: cur.rev_adj()){
            if(!e.vis()){
                next_pos[e.cop_pos][e.r_pos] = cur.cop_pos;
                calc(e);
            }
        }
    }
    else{
        for(auto e: cur.rev_adj()){
            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++){
            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();
        }
    }

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


    while(wining.size()>0){
        Pos cur = wining.back();
        cur.vis() = true;
        wining.pop_back();
        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_back(e);
                }
            }
        }
        else{
            for(auto e: cur.rev_adj()){
                if(!e.vis()){
                    rem[e.cop_pos][e.r_pos]--;
                    if(rem[e.cop_pos][e.r_pos] == 0){
                        e.vis() = true;
                        wining.push_back(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