Submission #107633

#	Time	Username	Problem	Language	Result	Execution time	Memory
107633		dfistric	Cop and Robber (BOI14_coprobber)	C++14	30 / 100	45 ms	1912 KiB

coprobber

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

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORd(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) FOR(i, 0, n)
#define ll long long

using namespace std;

int strategy;
int n;
vector <int> ve[MAX_N];
int D[MAX_N], F[MAX_N];
int disc = -1;
int P, W, H;

const int MAXN = 110;
int dp[MAXN][MAXN];
int mv[MAXN][MAXN];

int rek(int x, int y) {
    if (x == y) return 1;
    if (dp[x][y] != -1) return dp[x][y];

    dp[x][y] = 0;

    int ma = 1;
    for (int b : ve[y]) {
        ma = min(ma, rek(x, b));
    }
    if (ma == 1) {
        mv[x][y] = x;
        dp[x][y] = 1;
        return 1;
    }

    for (int a : ve[x]) {
        int ma = 1;
        for (int b : ve[y]) {
            ma = min(ma, rek(a, b));
        }
        if (ma == 1) {
            mv[x][y] = a;
            dp[x][y] = 1;
            return 1;
        }
    }

    return 0;
}

void dfs(int x, int p) {
    D[x] = ++disc;

    for (int y : ve[x]) {
        if (y == p) continue;
        dfs(y, x);
    }

    F[x] = disc;
    return; 
}

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

    REP(i, n) {
        REP(j, n) {
            if (A[i][j]) ve[i].push_back(j), e++;
        }
    }
    e /= 2;

    if (e == n - 1) {
        dfs(0, 0);
        strategy = 0, P = 0;
        return 0;
    }

    W = 1, H = 1;
    while (A[W - 1][W] == 1) W++;
    H = n / W;

    if (e == ((W - 1) * H + (H - 1) * W)) {
        strategy = 1, P = 0;
        return P;
    } 

    strategy = 2;
    memset(dp, -1, sizeof dp);
    REP(i, n) {
        int sol = 1;
        REP(j, n) {
            sol = min(sol, rek(i, j));
        }
        if (sol == 1) {
            P = i;
            return P;
        }
    }

    return -1;
}

int nextMove(int R) {

    if (strategy == 0) {
        for (int x : ve[P]) {
            if (D[x] < D[P]) continue;
        
            if (D[x] <= D[R] && F[R] <= F[x]) {
                P = x;
                return P;
            }
        }
        assert(0);
    } else if (strategy == 1) {
        if (abs((R % W) - (P % W)) == 1 && abs((R / W) - (P / W)) == 1) return P;


        if (R % W == P % W) {
            if (R > P) P += W;
            else       P -= W;

            return P;
        } else if (abs((R % W) - (P % W)) == 1) {
            if (R / W == P / W) {
                if (R > P) P++;
                else       P--;

                return P;
            } else {
                if (R > P) P += W;
                else       P -= W;

                return P;
            }
        } else {
            if (R % W > P % W) P++;
            else               P--;

            return P;
        }
    } else {
        P = mv[P][R];
        return P;
    }

    return 0;
}

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