Submission #785957

#	Time	Username	Problem	Language	Result	Execution time	Memory
785957		bane	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	400 ms	8556 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 orz[MAX_N][MAX_N];
int need[MAX_N][MAX_N][2];
int go[MAX_N][MAX_N];
int cop; 

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

    queue<pair<pii,int>>win;

    rep(i,n){
        int deg = 0;
        rep(j,n){
            if (A[i][j])deg++;
        }
        rep(j,n){
            if (i != j){
                need[j][i][1] = 1;
                need[j][i][0] = deg;
            }
        }
    }

    rep(i,n){
        win.push({mp(i,i),0}); 
        win.push({mp(i,i),1}); 
        go[i][i]=i;
        need[i][i][0] = 0;
        need[i][i][1] = 0;
    }

    int B[MAX_N][MAX_N];
    rep(i,n){
        rep(j,n){
            if(i==j)B[i][j]=1;
            else B[i][j] = A[i][j];
        }
    }


    while(!win.empty()){
        auto node = win.front();
        win.pop();
        int turn = node.sc;
        auto [me,him] = node.fr;
        //cout << me << " " << him << " " << turn << endl;
        if (turn){
            rep(i,n){
                if (A[i][him] && need[me][i][0]){
                    need[me][i][0]--;
                    if (need[me][i][0] == 0){
                        win.push(mp(mp(me,i),0));
                    }
                }
            }
        }else{
            rep(i,n){
                if (B[i][me] && need[i][him][1]){
                    need[i][him][1] = 0;
                    go[i][him] = me;
                    win.push(mp(mp(i,him), 1));
                }
            }
        }
    }

    rep(i,n){
        bool ok = 1;
        rep(j,n){
            ok &= (need[i][j][0] == 0);
        }
        if (ok){
            cop = i;
            return i;
        }
    }

    return -1;
}

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

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