Submission #1070766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070766		ortsac	Cop and Robber (BOI14_coprobber)	C++17	0 / 100	141 ms	262144 KiB

coprobber

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

using namespace std;

int atual = 0;
int n;

vector<vector<int>> adj;
int has[MAX_N][MAX_N];

int start(int N, bool A[MAX_N][MAX_N]) {
    // realmente não importa qual posição ele inicia
    // pq ele pode só ir andando pra qualquer uma e o cara escolhe de qualquer jeito então fodase
    n = N;
    adj.resize(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (A[i][j]) adj[i].push_back(j);
            has[i][j] = A[i][j];
        }
    }
    return 0;
}

int temR;

bool dfs(int node, int dad) {
    for (auto u : adj[node]) {
        if (u == dad) continue;
        if (dfs(u, node)) {
            if (node == atual) temR = u;
            return true;
        }
    }
    return false;
}

int nextMove(int r) { // IDEALMENTE O(N)
    if (has[r][atual]) return r;
    dfs(atual, -1);
    atual = temR;
    return atual;
}

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