Submission #135818

#	Time	Username	Problem	Language	Result	Execution time	Memory
135818		Vlatko	Cop and Robber (BOI14_coprobber)	C++14	16 / 100	57 ms	3960 KiB

coprobber

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


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

int calls, maxSCC;
int num[MAX_N], low[MAX_N];
bool instk[MAX_N];
vector<int> stk;

void tarjan(int u, int p) {
    num[u] = low[u] = calls++;
    instk[u] = true;
    stk.push_back(u);
    for (int v : adj[u]) {
        if (num[v] == -1) {
            tarjan(v, u);
        }
        if (instk[v] && v != p) {
            low[u] = min(low[u], low[v]);
        }
    }
    if (low[u] == num[u]) {
        int sz = 0;
        // cout << "new SCC: ";
        while (true) {
            int v = stk.back();
            stk.pop_back();
            instk[v] = false;
            ++sz;
            // cout << v << " ";
            if (v == u) {
                break;
            }
        }
        // cout << endl;
        maxSCC = max(maxSCC, sz);
    }
}

void bfs(int src, int dist[MAX_N]) {
    fill(dist, dist+N, -1);
    dist[src] = 0;
    queue<int> q;
    q.push(src);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

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);
            }
        }
    }
    maxSCC = 0;
    calls = 0;
    memset(num, -1, sizeof(num));
    memset(instk, false, sizeof(instk));
    for (int i = 0; i < N; ++i) {
        if (num[i] == -1) {
            tarjan(i, -1);
        }
    }
    // cout << "max SCC size: " << maxSCC << endl;
    if (maxSCC > 3) {
        // there is cycle with size bigger than 3
        // robber can always win
        return -1;
    }
    for (int i = 0; i < N; ++i) {
        bfs(i, dist[i]);
    }
    C = 0;
    return C;
}

int nextMove(int R) {
    int best_next = adj[C][0];
    for (int v : adj[C]) {
        if (dist[v][R] < dist[best_next][R]) {
            best_next = v;
        }
    }
    C = best_next;
    return C;
}

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