oj.uz

Submission #87747

# Submission time Handle Problem Language Result Execution time Memory
87747 2018-12-02T09:16:01 Z win11905 Cop and Robber (BOI14_coprobber) C++11
100 / 100
 1063 ms 8092 KB 
#include <bits/stdc++.h>
#define iii tuple<int, int, bool>
#include "coprobber.h"
using namespace std;

int pos = -1, mv[MAX_N][MAX_N], gnum[MAX_N][MAX_N][2]; // cop, rob, 0 = cop, 1 = rob
bool check[MAX_N][MAX_N][2];
queue<iii> Q;

int start(int n, bool A[MAX_N][MAX_N]) {
    memset(mv, -1, sizeof mv);
    for(int i = 0; i < n; ++i) {
        int cnt = 0;
        for(int j = 0; j < n; ++j) cnt += A[i][j];
        for(int j = 0; j < n; ++j) {
            gnum[i][j][0] = 1;
            gnum[j][i][1] = cnt;
        }
        Q.emplace(i, i, 0), Q.emplace(i, i, 1);
        check[i][i][0] = check[i][i][1] = true;
        mv[i][i] = i;
    }
    while(!Q.empty()) {
        int c, r, st; tie(c, r, st) = Q.front(); Q.pop();
        if(st) {  // now is rob and cop move turn
            for(int i = 0; i < n; ++i) if((A[i][c] or i == c) and !check[i][r][0])
                if(!--gnum[i][r][0]) Q.emplace(i, r, 0), mv[i][r] = c, check[i][r][0] = true;
        } else {// now is cop and rob move turn
            for(int i = 0; i < n; ++i) if(A[r][i] and !check[c][i][1])
                if(!--gnum[c][i][1]) Q.emplace(c, i, 1), check[c][i][1] = true;
        }
    }
    for(int i = 0; i < n; ++i) {
        bool st = true;
        for(int j = 0; j < n; ++j) if(mv[i][j] == -1) st = false;
        if(st) pos = i;
    }
    return pos;
}

int nextMove(int R) {
    return pos = mv[pos][R];
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1280 KB Output is correct
2 Correct 3 ms 1280 KB Output is correct
3 Correct 3 ms 1408 KB Output is correct
4 Correct 729 ms 5152 KB Output is correct
5 Correct 82 ms 3192 KB Output is correct
6 Correct 708 ms 5536 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1280 KB Output is correct
2 Correct 2 ms 1408 KB Output is correct
3 Correct 645 ms 5456 KB Output is correct
4 Correct 636 ms 5212 KB Output is correct
5 Correct 607 ms 5288 KB Output is correct
6 Correct 655 ms 5212 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1280 KB Output is correct
2 Correct 3 ms 1408 KB Output is correct
3 Correct 3 ms 1408 KB Output is correct
4 Correct 2 ms 1280 KB Output is correct
5 Correct 3 ms 1408 KB Output is correct
6 Correct 2 ms 1280 KB Output is correct
7 Correct 3 ms 1408 KB Output is correct
8 Correct 2 ms 1408 KB Output is correct
9 Correct 2 ms 1408 KB Output is correct
10 Correct 4 ms 1920 KB Output is correct
11 Correct 6 ms 1920 KB Output is correct
12 Correct 3 ms 1536 KB Output is correct
13 Correct 4 ms 1792 KB Output is correct
14 Correct 6 ms 1920 KB Output is correct
15 Correct 4 ms 1664 KB Output is correct
16 Correct 4 ms 1664 KB Output is correct
17 Correct 12 ms 2176 KB Output is correct
18 Correct 4 ms 1920 KB Output is correct
19 Correct 3 ms 1408 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1408 KB Output is correct
2 Correct 2 ms 1408 KB Output is correct
3 Correct 3 ms 1408 KB Output is correct
4 Correct 633 ms 5240 KB Output is correct
5 Correct 84 ms 3192 KB Output is correct
6 Correct 696 ms 5496 KB Output is correct
7 Correct 3 ms 1408 KB Output is correct
8 Correct 3 ms 1408 KB Output is correct
9 Correct 616 ms 5292 KB Output is correct
10 Correct 653 ms 5368 KB Output is correct
11 Correct 645 ms 5520 KB Output is correct
12 Correct 667 ms 5112 KB Output is correct
13 Correct 3 ms 1408 KB Output is correct
14 Correct 3 ms 1408 KB Output is correct
15 Correct 3 ms 1408 KB Output is correct
16 Correct 3 ms 1408 KB Output is correct
17 Correct 4 ms 1792 KB Output is correct
18 Correct 5 ms 1920 KB Output is correct
19 Correct 3 ms 1536 KB Output is correct
20 Correct 4 ms 1792 KB Output is correct
21 Correct 6 ms 1920 KB Output is correct
22 Correct 4 ms 1664 KB Output is correct
23 Correct 4 ms 1664 KB Output is correct
24 Correct 11 ms 2176 KB Output is correct
25 Correct 4 ms 1920 KB Output is correct
26 Correct 7 ms 2432 KB Output is correct
27 Correct 19 ms 3456 KB Output is correct
28 Correct 35 ms 4092 KB Output is correct
29 Correct 739 ms 8080 KB Output is correct
30 Correct 122 ms 4828 KB Output is correct
31 Correct 123 ms 4856 KB Output is correct
32 Correct 946 ms 7080 KB Output is correct
33 Correct 168 ms 4600 KB Output is correct
34 Correct 835 ms 8092 KB Output is correct
35 Correct 661 ms 5748 KB Output is correct
36 Correct 1063 ms 6908 KB Output is correct
37 Correct 447 ms 4352 KB Output is correct
38 Correct 3 ms 1408 KB Output is correct