Submission #613407

#	Time	Username	Problem	Language	Result	Execution time	Memory
613407		talant117408	Cop and Robber (BOI14_coprobber)	C++17	30 / 100	81 ms	2744 KiB

coprobber

#include "coprobber.h"
#ifndef EVAL
#include "grader.cpp"
#endif

#include <bits/stdc++.h>

using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define long                unsigned long 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'
#define PI                  2*acos(0.0)

const int MAXN = 503;
int n;
vector <int> graph[MAXN];
int dist[MAXN][MAXN];
int color[MAXN];
int flag = 0;
int cop = 0, last = 0;
//~ int grundy[MAXN][MAXN][2]; // cop, robber, whose move

void bfs(int v) {
    for (int i = 0; i < n; i++) dist[v][i] = 2e9;
    dist[v][v] = 0;
    queue <int> K;
    K.push(v);
    while (sz(K)) {
        auto u = K.front(); K.pop();
        for (auto to : graph[u]) {
            if (dist[v][to] > dist[v][u] + 1) {
                dist[v][to] = dist[v][u] + 1;
                K.push(to);
            } 
        }
    }
}

void dfs(int v = 0, int c = 1) {
    color[v] = c;
    for (auto to : graph[v]) {
        if (color[to]) {
            if (color[to] == color[v]) {
                flag = -1;
            }
        }
        else {
            dfs(to, 3 - c);
        }
    }
}

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]) {
                graph[i].pb(j);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        bfs(i);
    }
    dfs();
    
    return flag;
}

int nextMove(int R) {
    if (color[cop] == color[R]) return cop;
    
    int mn = 2e9, ind = -1;
    for (auto to : graph[cop]) {
        if (dist[R][to] < mn && last != to) {
            mn = dist[R][to];
            ind = to;
        }
    }
    last = cop;
    cop = ind;
    return cop;
}

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