Submission #134376

#	Time	Username	Problem	Language	Result	Execution time	Memory
134376		Kastanda	Cop and Robber (BOI14_coprobber)	C++11	100 / 100	785 ms	9224 KiB

coprobber

// ItnoE
#include<bits/stdc++.h>
#include "coprobber.h"
using namespace std;
const int N = 505;
int n, now, P[N][N], C[N][N];
bool dp[N][N][2];
vector < int > Adj[N];
int start(int _n, bool _A[500][500])
{
    n = _n;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            if (_A[i][j])
                Adj[i].push_back(j);
    queue < tuple < int , int , int > > qu;
    for (int i = 0; i < n; i ++)
    {
        dp[i][i][0] = dp[i][i][1] = 1;
        P[i][i] = -1;
        qu.push(make_tuple(i, i, 0));
        qu.push(make_tuple(i, i, 1));
    }
    while (qu.size())
    {
        int a, b, w;
        tie(a, b, w) = qu.front();
        qu.pop();
        if (w == 1)
        {
            if (!dp[a][b][0])
            {
                dp[a][b][0] = 1;
                P[a][b] = a;
                qu.push(make_tuple(a, b, 0));
            }
            for (int u : Adj[a])
                if (!dp[u][b][0])
                {
                    dp[u][b][0] = 1;
                    P[u][b] = a;
                    qu.push(make_tuple(u, b, 0));
                }
        }
        if (w == 0)
        {
            for (int u : Adj[b])
            {
                C[a][u] ++;
                if (C[a][u] == Adj[u].size())
                {
                    dp[a][u][1] = 1;
                    qu.push(make_tuple(a, u, 1));
                }
            }
        }
    }
    for (int i = 0; i < n; i ++)
    {
        bool w = 1;
        for (int j = 0; j < n; j ++)
            w &= dp[i][j][0];
        if (w)
        {
            now = i;
            return (i);
        }
    }
    return (-1);
}
int nextMove(int v)
{
    now = P[now][v];
    return (now);
}

Compilation message (stderr)

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:50:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (C[a][u] == Adj[u].size())
                     ~~~~~~~~^~~~~~~~~~~~~~~~

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