Submission #135794

#	Time	Username	Problem	Language	Result	Execution time	Memory
135794		Vlatko	Cop and Robber (BOI14_coprobber)	C++14	0 / 100	52 ms	3116 KiB

coprobber

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

const int unvisited = 0, explored = 1, visited = 2;

int N, C;
vector<int> adj[MAX_N];

bool found_cycle;
int dfs_calls = 0;
int status[MAX_N];
int sbsz[MAX_N]; // subtree size
int label[MAX_N]; // all node in subtree of u are in range [u, u+sbsz[u]-1]

void dfs(int u, int p) {
    label[u] = dfs_calls++;
    sbsz[u] = 1;
    status[u] = explored;
    for (int v : adj[u]) {
        if (status[v] == unvisited) {
            dfs(v, u);
            sbsz[u] += sbsz[v];
        } else if (status[v] == explored && v != p) {
            found_cycle = true;
        }
        if (found_cycle) return;
    }
    status[u] = visited;
}

int start(int _N, bool A[MAX_N][MAX_N]) {
    N = _N;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (A[i][j]) {
                adj[i].push_back(j);
            }
        }
    }
    fill(status, status+N, unvisited);
    found_cycle = false;
    dfs_calls = 0;
    dfs(0, -1);
    if (found_cycle) {
        return -1;
    }
    // graph is tree, put cop at root, he will always win by moving towards robber
    C = 0;
    return C;
}

int nextMove(int R) {
    for (int v : adj[C]) {
        if (label[v] > label[C] && label[v] <= R && R <= label[v] + sbsz[v] - 1) {
            C = v;
            return v;
        }
    }
}

Compilation message (stderr)

coprobber.cpp: In function 'int nextMove(int)':
coprobber.cpp:60:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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