Submission #1227938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227938		m5588ohammed	Cop and Robber (BOI14_coprobber)	C++20	16 / 100	30 ms	6724 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
int dis[501][501][2],parent[501][501][2];
int a[501][501],flag,disc[501];
vector <int> v[501];
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 dfs(int i,int cnt){
    disc[i]=cnt;
    for(int j:v[i]){
        if(disc[i]-disc[j]+1>4&&disc[j]!=0) flag=-1;
        if(disc[j]==0) dfs(j,cnt+1);
    }
    return;
}
int start(int N, bool A[MAX_N][MAX_N])
{
    n=N;
    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];
        }
    }
    for(int i=0;i<n;i++){
        bfs(i);
        if(disc[i]==0) dfs(i,1);
    }
    if(flag==-1) return -1;
    pos=0;
    return 0;
}

int nextMove(int R)
{
    if(a[R][pos]==1) return R;
    if(dis[R][pos][0]==1e9) return pos;
    //cout<<dis[R][pos][0]<<" "<<R<<" "<<pos<<endl;
    pos=parent[R][pos][0];
    return pos;
}

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