oj.uz

Submission #824825

# Submission time Handle Problem Language Result Execution time Memory
824825 2023-08-14T10:54:48 Z QwertyPi Cop and Robber (BOI14_coprobber) C++14
60 / 100
 1500 ms 262144 KB 
#include "coprobber.h"
#include <bits/stdc++.h>

using namespace std;

struct state{
    int u, v, t;
    int operator()() const {
        return u * MAX_N * 2 + v * 2 + t;
    }
    string print() const {
        string r;
        r += "(";
        r += to_string(u);
        r += ", ";
        r += to_string(v);
        r += ", ";
        r += to_string(t);
        r += ")";
        return r;
    }
};

int N;
bool w[MAX_N * MAX_N * 2];
int nxt[MAX_N * MAX_N * 2];
vector<int> H[MAX_N * MAX_N * 2];
int deg[MAX_N * MAX_N * 2], r_deg[MAX_N * MAX_N * 2];
bool added[MAX_N * MAX_N * 2];
bool A[MAX_N][MAX_N];

void add_edge(const state& u, const state& v){
    H[v()].push_back(u()); // cout << "Edge: " << u.print() << " -> " << v.print() << endl;
    if(w[v()] == true) deg[u()]++; r_deg[u()]++;
}

int pos = -1;
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++){
            ::A[i][j] = A[i][j];
        }
    }

    for(int u = 0; u < N; u++){
        for(int v = 0; v < N; v++){
            for(int t = 0; t < 2; t++){
                state st {u, v, t};
                if(u == v) w[st()] = true;
            }
        }
    }
    for(int u = 0; u < N; u++){
        for(int v = 0; v < N; v++){
            for(int t = 0; t < 2; t++){
                state st {u, v, t};
                if(u == v) continue;
                if(t == 0){
                    for(int i = 0; i < N; i++){
                        if(A[u][i] || i == u){
                            state st2 {i, v, !t};
                            add_edge(st, st2);
                        }
                    }
                }else{
                    for(int i = 0; i < N; i++){
                        if(A[v][i]){
                            state st2 {u, i, !t};
                            add_edge(st, st2);
                        }
                    }
                }
            }
        }
    }

    vector<int> det;
    
    for(int u = 0; u < N; u++){
        for(int v = 0; v < N; v++){
            for(int t = 0; t < 2; t++){
                state st {u, v, t};
                bool alr_win = false;
                if(t == 0){
                    for(int i = 0; i < N; i++){
                        if(A[u][i] && i == v) alr_win = true;
                    }
                }
                if(u != v && (r_deg[st()] == deg[st()] || alr_win)){
                    det.push_back(st()); added[st()] = true;
                }
            }
        }
    }

    while(det.size()){
        int k = det.back(); det.pop_back();
        int u = k / 2 / MAX_N;
        int v = k / 2 % MAX_N;
        int t = k % 2;
        state st {u, v, t};
        if(t == 0){
            bool exist_win = false;
            for(int i = 0; i < N; i++){
                if(A[u][i] || i == u){
                    state st2 {i, v, !t};
                    exist_win |= w[st2()];
                    if(w[st2()]) nxt[st()] = st2();
                }
            }
            w[st()] = exist_win;
        }else{
            bool all_win = true;
            for(int i = 0; i < N; i++){
                if(A[v][i]){
                    state st2 {u, i, !t};
                    all_win &= w[st2()];
                }
            }
            w[st()] = all_win;
        }

        for(auto st2 : H[st()]){
            if(added[st2]) continue;
            deg[st2]++; 
            if(deg[st2] == r_deg[st2]) added[st2] = true, det.push_back(st2);
            else if((!t) == 0 && w[st()] == 1) added[st2] = true, det.push_back(st2);
            else if((!t) == 1 && w[st()] == 0) added[st2] = true, det.push_back(st2);
        }
    }

    for(int i = 0; i < N; i++){
        bool all_win = true;
        for(int j = 0; j < N; j++){
            state st {i, j, 0};
            all_win &= w[st()];
        }
        if(all_win){
            pos = i;
            return i;
        }
    }
    return -1;
}

int nextMove(int R)
{
    state st {pos, R, 0};
    int st2 = nxt[st()];
    pos = st2 / 2 / MAX_N;
    return pos;
}

Compilation message

coprobber.cpp: In function 'void add_edge(const state&, const state&)':
coprobber.cpp:34:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   34 |     if(w[v()] == true) deg[u()]++; r_deg[u()]++;
      |     ^~
coprobber.cpp:34:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   34 |     if(w[v()] == true) deg[u()]++; r_deg[u()]++;
      |                                    ^~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11984 KB Output is correct
2 Correct 5 ms 12112 KB Output is correct
3 Correct 6 ms 12112 KB Output is correct
4 Correct 596 ms 36184 KB Output is correct
5 Correct 99 ms 19664 KB Output is correct
6 Correct 695 ms 36824 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12160 KB Output is correct
2 Correct 6 ms 12240 KB Output is correct
3 Correct 615 ms 38620 KB Output is correct
4 Correct 618 ms 36164 KB Output is correct
5 Correct 602 ms 37788 KB Output is correct
6 Correct 649 ms 37144 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11984 KB Output is correct
2 Correct 6 ms 12112 KB Output is correct
3 Correct 5 ms 12112 KB Output is correct
4 Correct 6 ms 12112 KB Output is correct
5 Correct 6 ms 12240 KB Output is correct
6 Correct 6 ms 12112 KB Output is correct
7 Correct 6 ms 12148 KB Output is correct
8 Correct 5 ms 12176 KB Output is correct
9 Correct 6 ms 12444 KB Output is correct
10 Correct 14 ms 14616 KB Output is correct
11 Correct 35 ms 19272 KB Output is correct
12 Correct 6 ms 12496 KB Output is correct
13 Correct 9 ms 13520 KB Output is correct
14 Correct 29 ms 16276 KB Output is correct
15 Correct 11 ms 13264 KB Output is correct
16 Correct 11 ms 13392 KB Output is correct
17 Correct 42 ms 20508 KB Output is correct
18 Correct 12 ms 14116 KB Output is correct
19 Correct 5 ms 12112 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11984 KB Output is correct
2 Correct 5 ms 12112 KB Output is correct
3 Correct 6 ms 12112 KB Output is correct
4 Correct 596 ms 36184 KB Output is correct
5 Correct 99 ms 19664 KB Output is correct
6 Correct 695 ms 36824 KB Output is correct
7 Correct 6 ms 12160 KB Output is correct
8 Correct 6 ms 12240 KB Output is correct
9 Correct 615 ms 38620 KB Output is correct
10 Correct 618 ms 36164 KB Output is correct
11 Correct 602 ms 37788 KB Output is correct
12 Correct 649 ms 37144 KB Output is correct
13 Correct 6 ms 11984 KB Output is correct
14 Correct 6 ms 12112 KB Output is correct
15 Correct 5 ms 12112 KB Output is correct
16 Correct 6 ms 12112 KB Output is correct
17 Correct 6 ms 12240 KB Output is correct
18 Correct 6 ms 12112 KB Output is correct
19 Correct 6 ms 12148 KB Output is correct
20 Correct 5 ms 12176 KB Output is correct
21 Correct 6 ms 12444 KB Output is correct
22 Correct 14 ms 14616 KB Output is correct
23 Correct 35 ms 19272 KB Output is correct
24 Correct 6 ms 12496 KB Output is correct
25 Correct 9 ms 13520 KB Output is correct
26 Correct 29 ms 16276 KB Output is correct
27 Correct 11 ms 13264 KB Output is correct
28 Correct 11 ms 13392 KB Output is correct
29 Correct 42 ms 20508 KB Output is correct
30 Correct 12 ms 14116 KB Output is correct
31 Correct 5 ms 12112 KB Output is correct
32 Correct 5 ms 11984 KB Output is correct
33 Correct 5 ms 12112 KB Output is correct
34 Correct 5 ms 12112 KB Output is correct
35 Correct 614 ms 36128 KB Output is correct
36 Correct 98 ms 19688 KB Output is correct
37 Correct 699 ms 36940 KB Output is correct
38 Correct 6 ms 12112 KB Output is correct
39 Correct 5 ms 12240 KB Output is correct
40 Correct 636 ms 38620 KB Output is correct
41 Correct 648 ms 36252 KB Output is correct
42 Correct 601 ms 37808 KB Output is correct
43 Correct 660 ms 37140 KB Output is correct
44 Correct 5 ms 12112 KB Output is correct
45 Correct 5 ms 12156 KB Output is correct
46 Correct 5 ms 12240 KB Output is correct
47 Correct 6 ms 12368 KB Output is correct
48 Correct 14 ms 14544 KB Output is correct
49 Correct 34 ms 19280 KB Output is correct
50 Correct 9 ms 12592 KB Output is correct
51 Correct 9 ms 13492 KB Output is correct
52 Correct 22 ms 16104 KB Output is correct
53 Correct 8 ms 13264 KB Output is correct
54 Correct 9 ms 13392 KB Output is correct
55 Correct 39 ms 20544 KB Output is correct
56 Correct 12 ms 14160 KB Output is correct
57 Correct 55 ms 19788 KB Output is correct
58 Correct 255 ms 32020 KB Output is correct
59 Correct 670 ms 58680 KB Output is correct
60 Execution timed out 2311 ms 262144 KB Time limit exceeded
61 Halted 0 ms 0 KB -