Submission #593022

#	Time	Username	Problem	Language	Result	Execution time	Memory
593022		Jomnoi	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	832 ms	9004 KiB

coprobber

#include <bits/stdc++.h>
#include "coprobber.h"
using namespace std;

queue <tuple <int, int, bool>> q;
int nxt[MAX_N][MAX_N][2];
vector <int> graph[MAX_N];
bool dp[MAX_N][MAX_N][2];
int adj[MAX_N][MAX_N];
int now;

void move(int nc, int nr, int nt, int c, int r, int t) {
    if(dp[nc][nr][nt] == true) {
        return;
    }

    dp[nc][nr][nt] = true;
    nxt[nc][nr][nt] = c;
    q.emplace(nc, nr, nt);
}

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

    for(int i = 0; i < N; i++) {
        dp[i][i][0] = dp[i][i][1] = true;
        q.emplace(i, i, 0);
        q.emplace(i, i, 1);
    }

    while(!q.empty()) {
        auto [c, r, t] = q.front();
        q.pop();

        if(t == 1) {
            for(auto nc : graph[c]) {
                move(nc, r, 0, c, r, 1);
            }
            move(c, r, 0, c, r, 1);
        }
        else { // t == 0
            for(auto nr : graph[r]) {
                if(++adj[c][nr] == graph[nr].size()) {
                    move(c, nr, 1, c, r, 1);
                }
            }
        }
    }

    for(int c = 0; c < N; c++) {
        bool ok = true;
        for(int r = 0; r < N; r++) {
            if(dp[c][r][0] == false) {
                ok = false;
                break;
            }
        }

        if(ok == true) {
            return now = c;
        }
    }
    return -1;
}

int nextMove(int R) {
    return now = nxt[now][R][0];
}

Compilation message (stderr)

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:50:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |                 if(++adj[c][nr] == graph[nr].size()) {
      |                    ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

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