Submission #107777

#	Time	Username	Problem	Language	Result	Execution time	Memory
107777		patrikpavic2	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	827 ms	21368 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, int > ppi;

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

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++) A[i][i] = 1;
    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++)
                    u[k][i]++;
            }
        }
    }
    for(int i = 0;i < n;i++){
        pob[i][i][1] = 1;
        Q.push({{i, i}, 1});
    }
    for(;!Q.empty();){
        int x = Q.front().X.X;
        int y = Q.front().X.Y;
        int z = Q.front().Y;
        Q.pop();
        for(int w = 0;w < n;w++){
            if(z && (A[w][x] || w == x)){
                if(pob[w][y][0]) continue;
                pob[w][y][0] = 1;
                tag[w][y] = x;
                Q.push({{w, y}, 0});
            }
            else if(!z && A[w][y]){
                if(pob[x][w][1]) continue;
                u[x][w]--;
                if(!u[x][w]){
                    pob[x][w][1] = 1;
                    Q.push({{x, w}, 1});
                }
            }
        }
    }
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(!pob[i][j][0] || !pob[i][j][1]) return -1;
        }
    }
    return 0;
}

int nextMove(int R){
    return cur = tag[cur][R];
}

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