Submission #785940

#	Time	Username	Problem	Language	Result	Execution time	Memory
785940		bane	Cop and Robber (BOI14_coprobber)	C++17	0 / 100	1 ms	336 KiB

coprobber

#include "coprobber.h"
#include "bits/stdc++.h"
     
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define fr first
#define mp make_pair
#define sc second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define each(x, a) for (auto &x : a)
#define vec vector
#define TURBO {ios::sync_with_stdio(0); cin.tie(0);}
     
using namespace std;
     
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
     
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pair<int, int>>;
using vvi = vector<vi>;
    

int go[MAX_N][MAX_N];
int win[MAX_N][MAX_N][2];
int cop; 



class directed_graph{

    public:
    int N;
    vector<vector<vector<vector<pair<pii,int>>>>>adj, comp;
    directed_graph(int _N): N(_N){
        adj.resize(N);
        comp.resize(N);
        for (int i = 0; i < N; i++){
            adj[i].resize(N);
            comp[i].resize(N);
            for (int j = 0; j < N; j++){
                adj[i][j].resize(2);
                comp[i][j].resize(2);
            }
        }
    }

    void add_edge(int c, int r, int t, int c1, int r1, int t1){
        comp[c][r][t].pb(mp(mp(c1,r1),t1));
        adj[c1][r1][t1].pb(mp(mp(c,r),t));
    }

    void Bredth_First_Search(int c0, int r0, int t0){
        queue<pair<pii,int>>q;
        q.push(mp(mp(c0,r0),t0));
        int visited[N][N][2];
        memset(visited,0,sizeof(visited));
        visited[c0][r0][t0] = 1;
        while(!q.empty()){
            auto node = q.front();
            q.pop();
            win[node.fr.fr][node.fr.sc][node.sc] = 1;
            each(x,adj[node.fr.fr][node.fr.sc][node.sc]){
                if (visited[x.fr.fr][x.fr.sc][x.sc])continue;
                visited[x.fr.fr][x.fr.sc][x.sc] = 1;
                q.push(x);
            }
        }
    }

    void Condense(bool A[][MAX_N]){
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                bool forced = 1;
                for (int k = 0; k < N; k++){
                    if (A[i][k]){
                        forced &= (win[j][k][0]);
                    }
                }    
                win[j][i][1] = forced;
            }
        }
    }

    void Build_strategy(){
        for (int c = 0; c < N; c++){
            for(int r = 0; r < N; r++){
               if (win[c][r][0]){
                    each(x,comp[c][r][0]){
                        if (win[x.fr.fr][x.fr.sc][x.sc]){
                            go[c][r] = x.fr.fr;
                            break;
                        }
                    }
                }
            }
        }
    }

};


int start(int N, bool A[MAX_N][MAX_N])
{

    directed_graph G(N);
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            for (int k = 0; k < N; k++){
                if (A[i][k])
                    G.add_edge(i,j,0,k,j,1);
                if (A[j][k])
                    G.add_edge(i,j,1,i,k,0);
            }
        }
    }

    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            if (i == j){
                G.Bredth_First_Search(i,j,0);
                G.Bredth_First_Search(i,j,1);
            }

            if (A[i][j]){
                G.Bredth_First_Search(i,j,0);
            }
        }
    }

    G.Condense(A);
    G.Build_strategy();

    for (int i = 0; i < N; i++){
        bool ok = 1;
        for (int j = 0; j < N; j++){
            ok &= win[i][j][0];
        }
        if (ok){
            cop = i;
            return i;
        }
    }

    return -1;
}

int nextMove(int R)
{
    cop = go[cop][R];
    return cop;;
}

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