Submission #1076216

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076216		raphaelp	Cop and Robber (BOI14_coprobber)	C++14	16 / 100	87 ms	8576 KiB

coprobber

#include <bits/stdc++.h>
#include "coprobber.h"
using namespace std;
vector<vector<int>> AR;
vector<vector<int>> cop, robber;
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);
            }
        }
    }
    cop.assign(500, vector<int>(500, -1)), robber.assign(500, vector<int>(500, -1));
    vector<vector<int>> choixcop(500, vector<int>(500)), choixrobber(500, vector<int>(500));
    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++)
    {
        cop[i][i] = 1;
        for (int j = 0; j < AR[i].size(); j++)
        {
            choixrobber[i][AR[i][j]]--;
            if (choixrobber[i][AR[i][j]] == 0)
                Q.push({i, AR[i][j], 1});
        }
        robber[i][i] = 1;
        choixrobber[i][i] = -1;
        for (int j = 0; j < AR[i].size(); j++)
        {
            Q.push({AR[i][j], i, 0, i});
        }
    }
    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;
            robber[temp[0]][temp[1]] = 1;
            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 = 4;
    vector<vector<int>> A = {{0, 1, 0, 0}, {1, 0, 1, 0}, {0, 1, 0, 1}, {0, 0, 1, 0}};
    cout << start(N, A);
}*/

Compilation message (stderr)

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

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