Submission #476554

#	Time	Username	Problem	Language	Result	Execution time	Memory
476554		SamAnd	Cop and Robber (BOI14_coprobber)	C++17	60 / 100	1532 ms	8016 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];

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

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));
            ++cnt[i][j][1];
            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));
                    ++cnt[i][j][1];
                }
                if (a[j][k])
                {
                    //ave(m_p(m_p(i, j), 0), m_p(m_p(i, k), 1));
                    ++cnt[i][j][0];
                }
            }
        }
    }

    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));
    }

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

        if (!z)
        {
            for (int h = 0; h < n; ++h)
            {
                if (h == u || a[u][h])
                {
                    if (!c[h][r][1])
                    {
                        p[h][r] = u;
                        c[h][r][1] = true;
                        q.push(m_p(m_p(h, r), 1));
                    }
                }
            }
        }
        else
        {
            for (int h = 0; h < n; ++h)
            {
                if (a[r][h])
                {
                    --cnt[u][h][0];
                    if (!c[u][h][0] && cnt[u][h][0] == 0)
                    {
                        c[u][h][0] = true;
                        q.push(m_p(m_p(u, h), 0));
                    }
                }
            }
        }
    }

    if (qq == 2 * n * n)
        return 0;
    return -1;
}

int u;
int nextMove(int r) {
    u = p[u][r];
    return u;
}

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