oj.uz

Submission #713547

# Submission time Handle Problem Language Result Execution time Memory
713547 2023-03-22T13:01:43 Z Stickfish Cop and Robber (BOI14_coprobber) C++17
30 / 100
 93 ms 3792 KB 
#include "coprobber.h"
#include <iostream>
#include <cassert>
#include <bitset>
#include <vector>
using namespace std;

bitset<MAX_N> edg[MAX_N];
bitset<MAX_N> redg[MAX_N];
bitset<MAX_N> used[2][MAX_N];
int depth[2][MAX_N][MAX_N];
int n;
int C;
int pR = -1;

int start(int N, bool A[MAX_N][MAX_N]) {
    n = N;
    int deg[MAX_N];

    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) {
        edg[i][j] = redg[j][i] = A[i][j];
    }
    for (int i = 0; i < N; ++i)
        deg[i] = edg[i].count();
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) {
        //bad_edg_cnt[0][i][j] = 1;
        //bad_edg_cnt[1][i][j] = deg[j];
        depth[1][i][j] = depth[0][i][j] = 1234567890;
    }
    vector<vector<int>> q;
    for (int i = 0; i < N; ++i) {
        //bad_edg_cnt[0][i][i] = bad_edg_cnt[1][i][i] = 0;
        q.push_back({0, i, i});
        q.push_back({1, i, i});
        used[0][i][i] = used[1][i][i] = 1;
    }
    int timer = 0;
    while (q.size()) {
        int t = q.back()[0];
        int u = q.back()[1];
        int v = q.back()[2];
        //cout << t << ' ' << u << ' ' << v << " | ";
        depth[t][u][v] = timer++;
        q.pop_back();
        bitset<MAX_N> cedg;
        if (t == 0) {
            cedg = redg[v];
            //used[u][v] = 1;
        } else {
            cedg = redg[u];
            cedg[u] = 1;
        }
        if (t == 0) {
            for (int nv = cedg._Find_first(); nv < n; nv = cedg._Find_next(nv)) {
                if (!used[1][u][nv] && (used[0][u] & edg[nv]) == edg[nv]) {
                    //cout << "(1 " << u << ' ' << nv << ") ";
                    q.push_back({1, u, nv});
                    used[1][u][nv] = 1;
                }
            }
        } else {
            for (int nu = cedg._Find_first(); nu < n; nu = cedg._Find_next(nu)) {
                if (!used[0][nu][v]) {
                    //cout << "(0 " << nu << ' ' << v << ") ";
                    q.push_back({0, nu, v});
                    used[0][nu][v] = 1;
                }
            }
        }
        //cout << endl;
    }
    for (int u = 0; u < n; ++u)
        edg[u][u] = 1;
    for (int u = 0; u < n; ++u) {
        bool isok = true;
        for (int v = 0; v < n; ++v) {
            isok &= used[0][u][v];
            //isok &= used[u][v] <= 0;
        }
        if (isok)
            return C = u;
    }
    return -1; 
}

int nextMove(int R) {
    pR = R;
    for (int nC = edg[C]._Find_first(); nC < n; nC = edg[C]._Find_next(nC)) { 
        if (depth[1][nC][R] < depth[0][C][R]) {
            return C = nC;
        }
    }
    assert(0);
}

Compilation message

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:18:9: warning: variable 'deg' set but not used [-Wunused-but-set-variable]
   18 |     int deg[MAX_N];
      |         ^~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 64 ms 3768 KB Output is correct
5 Correct 17 ms 1912 KB Output is correct
6 Correct 80 ms 3644 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 93 ms 3664 KB Output is correct
4 Correct 90 ms 3792 KB Output is correct
5 Correct 82 ms 3604 KB Output is correct
6 Correct 86 ms 3760 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 0 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 0 ms 336 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 0 ms 336 KB Output is correct
10 Correct 1 ms 720 KB Output is correct
11 Correct 5 ms 796 KB Output is correct
12 Correct 1 ms 464 KB Output is correct
13 Correct 2 ms 592 KB Output is correct
14 Correct 3 ms 720 KB Output is correct
15 Incorrect 1 ms 592 KB the situation repeated
16 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 64 ms 3768 KB Output is correct
5 Correct 17 ms 1912 KB Output is correct
6 Correct 80 ms 3644 KB Output is correct
7 Correct 0 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 93 ms 3664 KB Output is correct
10 Correct 90 ms 3792 KB Output is correct
11 Correct 82 ms 3604 KB Output is correct
12 Correct 86 ms 3760 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 0 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 0 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 0 ms 336 KB Output is correct
20 Correct 0 ms 336 KB Output is correct
21 Correct 0 ms 336 KB Output is correct
22 Correct 1 ms 720 KB Output is correct
23 Correct 5 ms 796 KB Output is correct
24 Correct 1 ms 464 KB Output is correct
25 Correct 2 ms 592 KB Output is correct
26 Correct 3 ms 720 KB Output is correct
27 Incorrect 1 ms 592 KB the situation repeated
28 Halted 0 ms 0 KB -