Submission #726125

#	Time	Username	Problem	Language	Result	Execution time	Memory
726125		Tigerpants	Cop and Robber (BOI14_coprobber)	C++17	Compilation error	0 ms	0 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;

    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);
            }
        }
    }
}

ll start(ll 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;
ll nextMove(ll R) {
    return moves[R][CopPositionNextMove];
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccstZU7u.o: in function `main':
grader.cpp:(.text.startup+0x16c): undefined reference to `start(int, bool (*) [500])'
/usr/bin/ld: grader.cpp:(.text.startup+0x2be): undefined reference to `nextMove(int)'
collect2: error: ld returned 1 exit status