Submission #824825

#	Time	Username	Problem	Language	Result	Execution time	Memory
824825		QwertyPi	Cop and Robber (BOI14_coprobber)	C++14	60 / 100	2311 ms	262144 KiB

coprobber

#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 (stderr)

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 / 16
• Subtask 2: 14 / 14
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40