Submission #1228100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228100		m5588ohammed	Cop and Robber (BOI14_coprobber)	C++20	16 / 100	158 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];
int n,pos;
void bfs(int bg){
    for(int i=0;i<n;i++) dis[bg][i][0]=dis[bg][i][1]=1e9;
    priority_queue <array<int,3>> qu;
    qu.push({0,bg,0});
    dis[bg][bg][0]=0;
    while(!qu.empty()){
        auto [mydis,i,u]=qu.top();
        mydis*=-1;
        qu.pop();
        if(dis[bg][i][u]<mydis) continue;
        for(int j:v[i]){
            if(dis[bg][j][u^1]>mydis+1){
                parent[bg][j][u^1]=i;
                dis[bg][j][u^1]=mydis+1;
                qu.push({dis[bg][j][u^1]*-1,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][0]==1e9) return pos;
    pos=parent[R][pos][0];
    return pos;
}

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