Submission #726126

#	Time	Username	Problem	Language	Result	Execution time	Memory
726126		Tigerpants	Cop and Robber (BOI14_coprobber)	C++17	0 / 100	1 ms	336 KiB

coprobber

#include "coprobber.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <map>
#include <set>

using namespace std;

typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

#define rep(i, a, b) for (ll i = a; i < b; i++)
#define mp(a, b) make_pair(a, b)
#define pb(a) push_back(a)
#define sz(a) a.size()

vvll g;

ll moves[MAX_N][MAX_N];
bool outcome[2][MAX_N][MAX_N]; // [turn][R][C] --> (R', C')
ll escapes[MAX_N][MAX_N];

void DFS(bool turn, ll R, ll C, ll src = -1) { // a call to DFS means that this position has just reached a positive outcome
    if (outcome[turn][R][C]) return;
    cout << "DFS(" << turn << ", " << R << ", " << C << ", " << src << ")\n";

    outcome[turn][R][C] = true;
    if (turn) {
        // if cop just moved
        // mark all adjacent positions as positive
        DFS(false, R, C, C);
        for (vll::iterator itr = g[C].begin(); itr != g[C].end(); itr++) {
            DFS(false, R, *itr, C);
        }
    } else {
        moves[R][C] = src;
        // if robber just moved
        // remove one from escapes from all adjacent. if escapes reaches 0, then winning
        for (vll::iterator itr = g[R].begin(); itr != g[R].end(); itr++) {
            escapes[*itr][C]--;
            if (escapes[*itr][C] == 0) {
                DFS(true, *itr, C);
            }
        }
    }
}

int start(int N, bool A[MAX_N][MAX_N]) {
    // initialize g
    g.resize(N);
    rep(i, 0, N) {
        rep(j, 0, N) {
            if (A[i][j]) {
                g[i].pb(j);
            }
        }
    }
    // initialize escapes
    rep(i, 0, N) {
        rep(j, 0, N) {
            escapes[i][j] = sz(g[i]);
        }
    }
    // initialize outcome
    rep(i, 0, N) {
        rep(j, 0, N) {
            outcome[0][i][j] = false;
            outcome[1][i][j] = false;
            moves[i][j] = -1;
        }
    }
    // do DFS
    rep(i, 0, N) {
        DFS(false, i, i, i);
        DFS(true, i, i);
    }
    // check if all outcomes are positive
    bool positive = true;
    rep(i, 0, N) {
        rep(j, 0, N) {
            positive &= outcome[0][i][j];
            positive &= outcome[1][i][j];
        }
    }

    return positive - 1;
}

ll CopPositionNextMove = 0;
int nextMove(int R) {
    return moves[R][CopPositionNextMove];
}

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