Submission #824846

#	Time	Username	Problem	Language	Result	Execution time	Memory
824846		QwertyPi	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	1371 ms	9612 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
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 id(int u, int v, int t){
    return u * MAX_N * 2 + v * 2 + t;
}

int N;
bool w[MAX_N * MAX_N * 2];
int nxt[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(int u, int v){
    // 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++){
                if(u == v) continue;
                if(t == 0){
                    for(int i = 0; i < N; i++){
                        if(A[u][i] || i == u){
                            add_edge(id(u, v, t), id(i, v, !t));
                        }
                    }
                }else{
                    for(int i = 0; i < N; i++){
                        if(A[v][i]){
                            add_edge(id(u, v, t), id(u, i, !t));
                        }
                    }
                }
            }
        }
    }

    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;
        int st = id(u, v, t);
        if(t == 0){
            bool exist_win = false;
            for(int i = 0; i < N; i++){
                if(A[u][i] || i == u){
                    int st2 = id(i, v, !t);
                    exist_win |= w[st2];
                    if(w[st2]) nxt[st] = st2;
                    if(exist_win) break;
                }
            }
            w[st] = exist_win;
        }else{
            bool all_win = true;
            for(int i = 0; i < N; i++){
                if(A[v][i]){
                    int st2 = id(u, i, !t);
                    all_win &= w[st2];
                    if(!all_win) break;
                }
            }
            w[st] = all_win;
        }

        if(t == 0){
            for(int i = 0; i < N; i++){
                if(A[i][v]){
                    int st2 = id(u, i, 1);
                    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);
                }
            }
        }else{
            for(int i = 0; i < N; i++){
                if(A[i][u] || i == u){
                    int st2 = id(i, v, 0);
                    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(int, int)':
coprobber.cpp:38:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   38 |     if(w[v] == true) deg[u]++; r_deg[u]++;
      |     ^~
coprobber.cpp:38:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   38 |     if(w[v] == true) deg[u]++; r_deg[u]++;
      |                                ^~~~~

• Subtask 1: 16 / 16
• Subtask 2: 14 / 14
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40