제출 #136037

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
136037		forelax	경찰관과 강도 (BOI14_coprobber)	C++14	100 / 100	1084 ms	142844 KiB

coprobber

#include "coprobber.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<bool> > wing(500,vector<bool> (500));
vector<vector<bool> > winb(500,vector<bool> (500));
vector<vector<int> > cntl(500,vector<int> (500));
vector<vector<int> > go(500,vector<int> (500));
vector<vector<bool> > a(500,vector<bool> (500));
vector<vector<int> > edge(500,vector<int> (500));
vector<int> eds(500);
int n,cr=0;
int start(int _N,bool A[500][500]){
    n=_N;
    int qs=0;
    vector<vector<int> > q(500*500*10,vector<int> (3));
    for(int i = 0 ; i < n ; i ++){
        for(int j = 0 ; j < n ; j ++){
            a[i][j]=A[i][j];
            if(a[i][j]){
                edge[i][eds[i]++]=j;
                wing[i][j]=true;
                q[qs][0]=0;
                q[qs][1]=i;
                q[qs][2]=j;
                qs++;
                go[i][j]=j;
            }
        }
    }
    for(int i = 0 ; i < n ; i ++){
        for(int j = 0 ; j < n ; j ++){
            if(i==j)continue;
            cntl[i][j]=eds[j];
            if(a[j][i])cntl[i][j]--;
        }
    }
    int cp=0;
    while(cp<qs){
        int x=q[cp][2];
        int y=q[cp][1];
        int st=q[cp][0];
        cp++;
        if(st==0){
            for(int i = 0 ; i < eds[x] ; i ++){
                int ne=edge[x][i];
                if(ne==y)continue;
                cntl[y][ne]--;
                if(cntl[y][ne])continue;
                q[qs][0]=1;
                q[qs][1]=y;
                q[qs][2]=ne;
                qs++;
                winb[y][ne]=true;
            }
        }else{
            for(int i = 0,ne ; i <= eds[y] ; i ++){
                if(i<eds[y])ne=edge[y][i];
                else ne=y;
                if(ne==x)continue;
                if(wing[ne][x])continue;
                go[ne][x]=y;
                wing[ne][x]=true;
                q[qs][0]=0;
                q[qs][1]=ne;
                q[qs][2]=x;
                qs++;
            }
        }
    }
    cr=-1;
//    for(int i = 0 ; i < n ; i ++){
//        for(int j = 0 ; j < n ; j ++){
//            cout<<wing[i][j];
//        }cout<<endl;}cout<<endl;
    for(int i = 0 ; i < n ; i ++){
        bool good=true;
        for(int j = 0 ; j < n ; j ++){
            if(i==j)continue;
            if(!wing[i][j]){
                good=false;
                break;
            }
        }
        if(!good)continue;
        cr=i;
        break;
    }
//    cout<<cr<<" ";
    return cr;
}
int nextMove(int np){
    cr=go[cr][np];
//    cout<<np<<" "<<cr<<" "<<endl;
    return cr;
}
//int main(){
//    int N;
//    cin>>N;
//    bool A[500][500];
////    vector<vector<bool> > A(N,vector<bool> (N));
//    for(int i = 0,g ; i < N ;i ++){
//        for(int j = 0 ; j < N ; j ++){
//            cin>>g;
//            A[i][j]=g;
//        }
//    }
//    int CP=start(N,A),one;
//    cin>>one;
//    vector<vector<int> > dir(n,vector<int> (n+1));
//    for(int i = 0 ; i < N ; i ++)
//        for(int j = 0 ; j <= N ; j ++)
//            cin>>dir[i][j];
//    int BP=dir[CP].back();
//    while(CP!=BP){
//        cout<<CP<<" "<<BP<<" ";
//        BP=dir[CP][BP];
//        CP=nextMove(BP);
//    }
//    cout<<CP<<" "<<BP;
//}

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