제출 #1228126

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228126		m5588ohammed	Cop and Robber (BOI14_coprobber)	C++20	0 / 100	143 ms	6764 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
int dis[501][501][2],dis2[501],parent[501][501][2];
int a[501][501],flag;
vector <int> v[501];
queue <int> qu1,qu2;
int n,pos;
void bfs(int bg){
    for(int i=0;i<n;i++) dis[bg][i][0]=dis[bg][i][1]=1e9;
    queue <array<int,2>> qu;
    qu.push({bg,0});
    dis[bg][bg][0]=0;
    while(!qu.empty()){
        auto [i,u]=qu.front();
        qu.pop();
        for(int j:v[i]){
            if(dis[bg][j][u^1]==1e9){
                parent[bg][j][u^1]=i;
                dis[bg][j][u^1]=dis[bg][i][u]+1;
                qu.push({j,u^1});
            }
        }
    }
}
void bfs2(int bg){
    for(int i=0;i<n;i++) dis2[i]=1e9;
    queue <int> qu;
    qu.push(bg);
    dis2[bg]=0;
    while(!qu.empty()){
        int i=qu.front();
        qu.pop();
        for(int j=0;j<n;j++){
            if(a[i][j]==0) continue;
            if(dis2[j]==1e9){
                dis2[j]=dis2[i]+1;
                qu.push(j);
            }
        }
    }
    return;
}
int start(int N, bool A[MAX_N][MAX_N])
{
    n=N;
    pos=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(A[i][j]==1) v[i].push_back(j);
            a[i][j]=A[i][j];
        }
        if(v[i].size()==n-1) pos=i;
    }
    int mx=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(a[i][j]==1){
                a[i][j]=a[j][i]=0;
                bfs2(i);
                if(dis2[j]!=1e9) mx=max(dis2[j]+1,mx);
                a[i][j]=a[j][i]=1;
            }
        }
    }
    for(int i=0;i<n;i++) bfs(i);
    if(mx>4) return -1;
    return 0;
}

int nextMove(int R)
{
    if(a[R][pos]==1) return R;
    if(dis[R][pos][1]==1e9||R==pos) return pos;
    if(qu1.size()==0&&qu2.size()==0){
        int bg=pos,u=1;
        while(bg!=R){
            bg=parent[R][bg][u];
            if(bg!=R) qu1.push(bg);
            u^=1;
        }
    }
    qu2.push(R);
    if(qu1.size()!=0){
        pos=qu1.front();
        qu1.pop();
        return pos;
    }
    else{
        pos=qu2.front();
        qu2.pop();
        return pos;
    }
}

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