Submission #208691

#	Time	Username	Problem	Language	Result	Execution time	Memory
208691		E869120	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	757 ms	8184 KiB

coprobber

#include "coprobber.h"
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

int N;
vector<int> X[509];
bool dp1[509][509], dp2[509][509];
int deg[509][509], to[509][509];
queue<tuple<int, int, int>> Q;

int cx = -1;

void police_add(int police, int robber) {
    for (int i : X[police]) {
        if (dp1[i][robber] == true) continue;
        dp1[i][robber] = true;
        to[i][robber] = police;
        Q.push(make_tuple(i, robber, 2));
    }
    if (dp1[police][robber] == false) {
        to[police][robber] = police;
        dp1[police][robber] = true;
        Q.push(make_tuple(police, robber, 2));
    }
}

void robber_add(int police, int robber) {
    for (int i : X[robber]) {
        deg[police][i]++;
        if (deg[police][i] == X[i].size()) {
            dp2[police][i] = true;
            Q.push(make_tuple(police, i, 1));
        }
    }
}

int start(int NN, bool A[MAX_N][MAX_N]) {
    N = NN; int cnt = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (A[i][j] == 1) { X[i].push_back(j); if (i < j) cnt++; }
        }
    }

    for (int i = 0; i < N; i++) {
        Q.push(make_tuple(i, i, 1));
        dp2[i][i] = true;
    }
    while (!Q.empty()) {
        int s1 = get<0>(Q.front()), s2 = get<1>(Q.front()), s3 = get<2>(Q.front()); Q.pop();
        if (s3 == 1) {
            police_add(s1, s2);
        }
        else {
            robber_add(s1, s2);
        }
    }

    for (int i = 0; i < N; i++) {
        bool flag = false;
        for (int j = 0; j < N; j++) {
            if (dp1[i][j] == false) flag = true;
        }
        if (flag == false) cx = i;
    }
    return cx;
}

int nextMove(int R) {
    cx = to[cx][R];
    return cx;
}

Compilation message (stderr)

coprobber.cpp: In function 'void robber_add(int, int)':
coprobber.cpp:32:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (deg[police][i] == X[i].size()) {
             ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

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