oj.uz

Submission #135818

# Submission time Handle Problem Language Result Execution time Memory
135818 2019-07-24T11:46:47 Z Vlatko Cop and Robber (BOI14_coprobber) C++14
16 / 100
 57 ms 3960 KB 
#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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 54 ms 3580 KB Output is correct
5 Correct 15 ms 1784 KB Output is correct
6 Correct 57 ms 3960 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Cop can catch the robber, but start() returned -1
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 2 ms 376 KB Cop can catch the robber, but start() returned -1
5 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 54 ms 3580 KB Output is correct
5 Correct 15 ms 1784 KB Output is correct
6 Correct 57 ms 3960 KB Output is correct
7 Incorrect 2 ms 376 KB Cop can catch the robber, but start() returned -1
8 Halted 0 ms 0 KB -