Submission #476544

#	Time	Username	Problem	Language	Result	Execution time	Memory
476544		SamAnd	Cop and Robber (BOI14_coprobber)	C++17	60 / 100	1316 ms	262148 KiB

coprobber

#include "coprobber.h"
#include <iostream>
#include <set>
#include <cstring>
#include <cassert>
#include <vector>
#include <queue>

using namespace std;

#define m_p make_pair
#define fi first
#define se second

int cnt[MAX_N][MAX_N][2];
vector<pair<pair<int, int>, bool> > rg[MAX_N][MAX_N][2];

void ave(pair<pair<int, int>, bool> x, pair<pair<int, int>, bool> y)
{
    rg[y.fi.fi][y.fi.se][y.se].push_back(x);
    ++cnt[x.fi.fi][x.fi.se][x.se];
}

bool c[MAX_N][MAX_N][2];
int p[MAX_N][MAX_N];

int u;
int start(int n, bool a[MAX_N][MAX_N]) {

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            ave(m_p(m_p(i, j), 1), m_p(m_p(i, j), 0));
            for (int k = 0; k < n; ++k)
            {
                if (a[i][k])
                {
                    ave(m_p(m_p(i, j), 1), m_p(m_p(k, j), 0));
                }
                if (a[j][k])
                {
                    ave(m_p(m_p(i, j), 0), m_p(m_p(i, k), 1));
                }
            }
        }
    }

    queue<pair<pair<int, int>, bool> > q;

    for (int i = 0; i < n; ++i)
    {
        c[i][i][0] = true;
        q.push(m_p(m_p(i, i), 0));
        c[i][i][1] = true;
        q.push(m_p(m_p(i, i), 1));
    }

    while (!q.empty())
    {
        int u = q.front().fi.fi;
        int r = q.front().fi.se;
        bool z = q.front().se;
        q.pop();

        for (int i = 0; i < rg[u][r][z].size(); ++i)
        {
            pair<pair<int, int>, bool> h = rg[u][r][z][i];
            if (h.se)
            {
                if (!c[h.fi.fi][h.fi.se][h.se])
                {
                    p[h.fi.fi][h.fi.se] = u;
                    c[h.fi.fi][h.fi.se][h.se] = true;
                    q.push(h);
                }
            }
            else
            {
                --cnt[h.fi.fi][h.fi.se][h.se];
                if (cnt[h.fi.fi][h.fi.se][h.se] == 0 && !c[h.fi.fi][h.fi.se][h.se])
                {
                    c[h.fi.fi][h.fi.se][h.se] = true;
                    q.push(h);
                }
            }
        }
    }

    for (u = 0; u < n; ++u)
    {
        bool z = true;
        for (int r = 0; r < n; ++r)
        {
            if (!c[u][r][1])
            {
                z = false;
                break;
            }
        }
        if (z)
        {
            return u;
        }
    }
    return -1;
}

set<pair<int, int> > s;
int nextMove(int r) {
    if (!c[u][r][1])
        return -1234;
    if (s.find(m_p(u, r)) != s.end())
        return -1234;
    s.insert(m_p(u, r));
    return (u = p[u][r]);
}

Compilation message (stderr)

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for (int i = 0; i < rg[u][r][z].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~~~~~

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