oj.uz

Submission #379575

# Submission time Handle Problem Language Result Execution time Memory
379575 2021-03-18T16:13:32 Z Kubin Cop and Robber (BOI14_coprobber) C++17
0 / 100
 1 ms 492 KB 
#include <bits/stdc++.h>

using namespace std;

const size_t M = 512;

int n;
bool G[M][M];
bool vis[2][M][M], win[2][M][M], lose[2][M][M];
int opt[2][M][M], deg[2][M][M], gdeg[M], vertex;

void dfs(bool t, int u, int v)
{
    vis[t][u][v] = true;
    if(t) // robber
    {
        for(int u1 = 0; u1 < n; u1++) if((u1 == u or G[u1][u]) and not vis[0][u1][v])
        {
            if(lose[1][u][v])
                win[0][u1][v] = true, opt[0][u1][v] = u;
            else if(--deg[0][u1][v] == 0)
                lose[0][u1][v] = true;
            else
                continue;
            dfs(0, u1, v);
        }
    }
    else // cop
    {
        for(int v1 = 0; v1 < n; v1++) if(G[v1][v] and not vis[1][u][v1])
        {
            if(lose[0][u][v])
                win[1][u][v1] = true, opt[1][u][v1] = v;
            else if(--deg[1][u][v1] == 0)
                lose[1][u][v1] = true;
            else
                continue;
            dfs(1, u, v1);
        }
    }
}

int start(int _n, bool _G[500][500])
{
    n = _n;
    for(int u = 0; u < n; u++)
        for(int v = 0; v < n; v++)
            G[u][v] = _G[u][v], opt[0][u][v] = opt[1][u][v] = -1;

    for(int u = 0; u < n; u++)
        for(int v = 0; v < n; v++)
            gdeg[u] += G[u][v];
    for(int u = 0; u < n; u++)
        for(int v = 0; v < n; v++)
            opt[0][u][v] = gdeg[u] + 1, opt[1][u][v] = gdeg[v];

    for(int u = 0; u < n; u++)
        win[0][u][u] = lose[1][u][u] = true;

    for(int u = 0; u < n; u++)
        if(not vis[1][u][u])
            dfs(1, u, u);

    for(int u = 0; u < n; u++)
    {
        bool all = true;
        for(int v = 0; v < n; v++)
            if(not win[0][u][v])
                all = false;
        if(all)
            return vertex = u;
    }
    return -1;
}

int nextMove(int r)
{
    return vertex = opt[0][vertex][r];
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Incorrect 1 ms 492 KB Cop can catch the robber, but start() returned -1
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Cop can catch the robber, but start() returned -1
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Incorrect 1 ms 492 KB Cop can catch the robber, but start() returned -1
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Incorrect 1 ms 492 KB Cop can catch the robber, but start() returned -1
4 Halted 0 ms 0 KB -