Submission #1076274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076274		raphaelp	Cop and Robber (BOI14_coprobber)	C++14	60 / 100	541 ms	262144 KiB

coprobber

#include <bits/stdc++.h>
#include "coprobber.h"
using namespace std;
vector<vector<int>> AR;
int cop[500][500], robber[500][500];
int pos = 0;
int start(int N, bool A[500][500])
{
    AR.assign(N, {});
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (A[i][j])
            {
                AR[j].push_back(i);
            }
        }
    }
    int choixrobber[500][500];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < 500; j++)
        {
            robber[i][j] = -1;
            cop[i][j] = -1;
        }
    queue<vector<int>> Q;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            choixrobber[i][j] = AR[j].size();
        }
    }
    for (int i = 0; i < N; i++)
    {
        Q.push({i, i, 0, 0});
        Q.push({i, i, 1});
    }
    while (!Q.empty())
    {
        vector<int> temp = Q.front();
        Q.pop();
        if (temp[2] == 0)
        {
            if (cop[temp[0]][temp[1]] != -1)
                continue;
            cop[temp[0]][temp[1]] = temp[3];
            for (int i = 0; i < AR[temp[1]].size(); i++)
            {
                choixrobber[temp[0]][AR[temp[1]][i]]--;
                if (choixrobber[temp[0]][AR[temp[1]][i]] == 0)
                    Q.push({temp[0], AR[temp[1]][i], 1});
            }
        }
        else
        {
            if (robber[temp[0]][temp[1]] != -1)
                continue;
            choixrobber[temp[0]][temp[1]] = 0;
            robber[temp[0]][temp[1]] = 1;
            Q.push({temp[0], temp[1], 0, temp[0]});
            for (int i = 0; i < AR[temp[0]].size(); i++)
            {
                Q.push({AR[temp[0]][i], temp[1], 0, temp[0]});
            }
        }
    }
    int x = -1;
    bool b = 1;
    while (b)
    {
        x++;
        if (x == N)
            return -1;
        b = 0;
        for (int i = 0; i < N; i++)
            if (cop[x][i] == -1)
                b = 1;
    }
    pos = x;
    return x;
}
int nextMove(int R)
{
    pos = cop[pos][R];
    return pos;
}
/*int main()
{
    int N = 500;
    vector<vector<int>> A = {{0, 1, 1, 0}, {1, 0, 0, 1}, {1, 0, 0, 1}, {0, 1, 1, 0}};
    cout << start(N, A);
}*/

Compilation message (stderr)

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:49:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             for (int i = 0; i < AR[temp[1]].size(); i++)
      |                             ~~^~~~~~~~~~~~~~~~~~~~
coprobber.cpp:63:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             for (int i = 0; i < AR[temp[0]].size(); i++)
      |                             ~~^~~~~~~~~~~~~~~~~~~~

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