Submission #107759

#	Time	Username	Problem	Language	Result	Execution time	Memory
107759		patrikpavic2	Cop and Robber (BOI14_coprobber)	C++17	0 / 100	15 ms	12160 KiB

coprobber

#include "coprobber.h"
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>

#define X first
#define Y second
#define PB push_back

using namespace std;

const int INF = 0x3f3f3f3f;

typedef pair < int, int > pii;
typedef pair < pii, bool > ppi;

int pob[MAX_N][MAX_N][2], n;
vector < ppi > v[MAX_N][MAX_N][2];
queue < ppi > Q;
int u[MAX_N][MAX_N], cur, a[MAX_N][MAX_N];

int start(int N, bool A[MAX_N][MAX_N]){
    n = N;
    // 0 je cajo na potezu 1 je lopov
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(A[i][j]){
                a[i][j] = 1;
                for(int k = 0;k < n;k++){
                    v[i][k][1].PB({{j, k}, 0});  // edgevi su obrnuti
                    v[k][i][0].PB({{k, j}, 1});
                }
            }
        }
    }
    for(int i = 0;i < n;i++){
        pob[i][i][1] = 1;
    }
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            u[i][j] = (int)v[i][j][1].size();
        }
    }
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(pob[i][j][0]) Q.push({{i, j}, 0});
            //if(pob[i][j][1]) Q.push({{i, j}, 1});
        }
    }
    for(;!Q.empty();){
        int x = Q.front().X.X;
        int y = Q.front().X.Y;
        int z = Q.front().Y;
        Q.pop();
        for(ppi A : v[x][y][z]){
            int nx = A.X.X;
            int ny = A.X.Y;
            if(pob[nx][ny][!z]) continue;
            if(z){
                pob[nx][ny][!z] = 1;
                Q.push({{nx, ny}, !z});
            }
            else{
                u[nx][ny]--;
                if(!u[nx][ny]){
                    pob[nx][ny][!z] = 1;
                    Q.push({{nx, ny}, !z});
                }
            }
        }
    }
    for(int i = 0;i < n;i++){
        int bad = 0;
        for(int j = 0;j < n;j++) bad |= !pob[i][j][0];
        if(!bad) return cur = i;
    }
    return -1;
}

int nextMove(int R){
    for(int i = 0;i < n;i++){
        if(a[cur][i] && pob[i][R][1]) return cur = i;
    }
    return -1;
}

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