Submission #961360

#	Time	Username	Problem	Language	Result	Execution time	Memory
961360		berr	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	476 ms	58336 KiB

coprobber

#include <bits/stdc++.h>
using namespace std;
# include "coprobber.h"
 
int pos;
int val[505][505][2];
int vis[505][505][2];
int b[505][505], c[505][505];
 
int start(int n, bool a[MAX_N][MAX_N]) {
 
    vector<int> e(n); 
    for(int i=0; i<n; i++){
        for(int l=0; l<n; l++){
            b[i][l]=-1;
            if(a[i][l]){
                e[i]++;
            }
        }
    }
 
    queue<array<int, 3>> q;
 
    for(int i=0; i<n; i++){
        val[i][i][0]=1;
        val[i][i][1]=0;
        b[i][i]=i;
        q.push({i, i, 1});
        q.push({i, i, 0});
    }
 
    while(q.size()){
        auto [x, y, z]=q.front();
        q.pop();
        if(vis[x][y][z]){ 
            continue;
        }
        else{           
           // cout<<val[x][y][z]<<"\n";
            vis[x][y][z]=1;
            if(z==0){
                val[x][y][z]=1;
                for(int i=0; i<n; i++){
                    if(!a[i][y]||vis[x][i][1]) continue;
                    c[x][i]++;
                    if(c[x][i]==e[i]){
                        val[x][i][1]=0;
                        q.push({x, i, 1}); 
                    }
                }
            }
            else {
                val[x][y][z] = 0;
                for(int i=0; i<n; i++){
                    if(!a[i][x]||vis[i][y][0]) continue;
                    if(b[i][y]==-1) b[i][y]=x;
                    q.push({i, y, 0});
                }
                if(b[x][y]==-1) b[x][y]=x;
                q.push({x, y, 0});
                
            }
 
        }
    }
 
    for(int i=0; i<n; i++){
        int flag=1;
        for(int j=0; j<n; j++){
            if(val[i][j][0]==0){
                flag=0;
            }
            
        }
        if(flag){
            return pos=i;
        }
    }
 
    return -1;
}
 
int nextMove(int R) {
    return pos=b[pos][R];
} 

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