제출 #1283200

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283200		abc123	Cop and Robber (BOI14_coprobber)	C++20	컴파일 에러	0 ms	0 KiB

coprobber

#include <bits/stdc++.h>
using namespace std;

int N;
vector<vector<bool>> adj;

// State: 2 turns - 0 (police), 1 (robber)
const int MAXN = 510;
int degree[MAXN][MAXN][2];
int dist[MAXN][MAXN][2];
int nxt[MAXN][MAXN][2]; // next move for police in police turn states

queue<tuple<int,int,int>> q;

void init() {
    memset(degree, 0, sizeof(degree));
    memset(dist, -1, sizeof(dist));
    memset(nxt, -1, sizeof(nxt));

    // Initialize degrees for states
    for (int p = 0; p < N; p++) {
        for (int r = 0; r < N; r++) {
            degree[p][r][0] = 1; // police can wait or move to neighbors
            for (int np = 0; np < N; np++) 
                if (adj[p][np]) degree[p][r][0]++;
            degree[p][r][1] = 0; // count possible robber moves
            for (int nr = 0; nr < N; nr++) 
                if (adj[r][nr]) degree[p][r][1]++;
        }
    }
}

int start_pos = -1;

void solve() {
    init();

    // Initialize queue with capturing states (police == robber)
    for (int i = 0; i < N; i++) {
        for (int turn = 0; turn < 2; turn++) {
            dist[i][i][turn] = 0;
            q.emplace(i, i, turn);
        }
    }

    // Retrograde BFS from capturing states
    while (!q.empty()) {
        auto [p, r, turn] = q.front();
        q.pop();
        int curDist = dist[p][r][turn];

        if (turn == 0) { // police's turn, previous turn was robber
            // Previous states: robber's turn from same p but different r
            // we came here from (p, r2, 1) where r2 can move to r
            for (int r2 = 0; r2 < N; r2++) {
                if (adj[r2][r]) {
                    if (dist[p][r2][1] == -1) {
                        degree[p][r2][1]--;
                        if (degree[p][r2][1] == 0) {
                            dist[p][r2][1] = curDist + 1;
                            q.emplace(p, r2, 1);
                        }
                    }
                }
            }
        } else { // robber's turn, previous was police's turn
            // Police can wait or move to neighbors
            for (int p2 = 0; p2 < N; p2++) {
                if (p2 == p || adj[p][p2]) {
                    if (dist[p2][r][0] == -1) {
                        dist[p2][r][0] = curDist + 1;
                        nxt[p2][r][0] = p; // police came from p
                        q.emplace(p2, r, 0);
                    }
                }
            }
        }
    }

    // Find starting police position where police can guarantee capture
    for (int p = 0; p < N; p++) {
        bool canStart = true;
        for (int r = 0; r < N; r++) {
            if (dist[p][r][0] == -1) {
                canStart = false;
                break;
            }
        }
        if (canStart) {
            start_pos = p;
            break;
        }
    }
}

// Current police position and strategy state
int policePos;
bool policeTurn = true;

int nextMove(int robberPos) {
    if (policeTurn) {
        // On police turn, pick next move
        int nextP = -1;
        // Police waits (stays) or move to neighbors
        if (dist[policePos][robberPos][0] != -1) {
            nextP = nxt[policePos][robberPos][0];
            if(nextP == -1) nextP = policePos; // wait if no better move known
        } else {
            nextP = policePos;
        }
        policePos = nextP;
        policeTurn = false;
        return nextP;
    } else {
        // Robber turn just ended, police turn now
        policeTurn = true;
        // No move on robber's turn
        return policePos;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    adj.assign(N, vector<bool>(N, false));

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            int v;
            cin >> v;
            adj[i][j] = (v == 1);
        }

    solve();

    cout << start_pos << "\n";
    // This is where you'd interactively run nextMove as per contest environment.

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

/usr/bin/ld: /tmp/cc1hpCCM.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccv8KjBB.o:coprobber.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc1hpCCM.o: in function `main':
grader.cpp:(.text.startup+0x155): undefined reference to `start(int, bool (*) [500])'
collect2: error: ld returned 1 exit status