Submission #106138

#	Time	Username	Problem	Language	Result	Execution time	Memory
106138		luciocf	Cop and Robber (BOI14_coprobber)	C++14	0 / 100	16 ms	16640 KiB

coprobber

#include <bits/stdc++.h>
#include "coprobber.h"

using namespace std;

const int maxn = 510;

struct State
{
    int u, w, q;
};

int n;

int win[maxn][maxn][2];

int mark[maxn][maxn][2];

vector<int> grafo[maxn];

vector<State> game[maxn][maxn][2];

void build(int u, int w, int q)
{
    if (u == w) return;

    if (q == 0)
    {   
        game[u][w][0].push_back({u, w, 1});
        for (auto v: grafo[u])
            game[u][w][0].push_back({v, w, 1});
    }
    else
    {
        for (auto v: grafo[w])
            game[u][w][1].push_back({u, v, 0});
    }
}

void dfs(int u, int w, int q)
{
    if (mark[u][w][q] == 2) return;

    if (u == w)
    {
        if (q == 0) win[u][w][q] = 1;
        else win[u][w][q] = 0;

        mark[u][w][q] = 2;
        return;
    }

    mark[u][w][q] = 1;

    for (auto S: game[u][w][q])
    {
        if (q == 0)
        {
            int v = S.u;
            
            if (mark[v][w][1])
            {
                if (mark[v][w][1] == 2 && win[v][w][1] == 0) win[u][w][0] = 1;
                continue;
            }

            dfs(v, w, 1);

            if (win[v][w][1] == 0) win[u][w][0] = 1;
        }
        else
        {
            int v = S.w;

            if (mark[u][v][0])
            {
                if (mark[u][v][0] == 1 || win[u][v][0] == 0) win[u][w][1] = 1;
                continue;
            }

            dfs(u, v, 0);

            if (win[u][v][0] == 0) win[u][w][1] = 1;
        }
    }

    mark[u][w][q] = 2;
}

int start(int N, bool A[MAX_N][MAX_N])
{
    n = N;

    for (int i = 0; i < n; i++)
    	for (int j = 0; j < n; j++)
    		if (A[i][j])
    			grafo[i].push_back(j);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int q = 0; q < 2; q++)
                build(i, j, q);

    for (int i = 0; i < 1; i++)
    {
        memset(win, 0, sizeof win); memset(mark, 0, sizeof mark);

        for (int j = 0; j < n; j++)
            dfs(i, j, 0);

        bool ok = 1;
        for (int j = 0; j < n; j++)
            if (win[i][j][0] == 0) 
                ok = 0;

        if (ok) return i;
    }

    return -1;
}

int nextMove(int R)
{
    return 0;
}

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