Submission #648232

#	Time	Username	Problem	Language	Result	Execution time	Memory
648232		Ronin13	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	598 ms	14404 KiB

coprobber

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;

#define MAX_N 500

// modify the following functions
// you can define global variables and functions

int deg[MAX_N][MAX_N][2];
bool used[MAX_N][MAX_N][2];
vector <vector <int> > g(MAX_N);
bool dp[MAX_N][MAX_N][2];
int cur;

struct state{
    int a, b, c;
    state(int a, int b, int c) : a(a), b(b), c(c){
    }
    state(){
        a = b = c = 0;
    }
}wining[MAX_N][MAX_N][2];

int start(int N, bool A[MAX_N][MAX_N]) {
    int n = N;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(A[i][j]) g[i].pb(j);
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            deg[i][j][0] = g[i].size() + 1;
            deg[i][j][1] = g[j].size();
        }
    }
    queue <state> q;
    for(int i= 0; i < n; i++){
        dp[i][i][0] = 1;
        dp[i][i][1] = 0;
        q.push({i, i, 0});
        q.push({i, i, 1});
        used[i][i][1] = used[i][i][0] = 1;
    }
    while(!q.empty()){
        state cur = q.front(); q.pop();
        int a = cur.a, b = cur.b, type = cur.c;
        if(type == 0){
            for(int to : g[b]){
                if(used[a][to][1]) continue;
                if(dp[a][b][0])deg[a][to][1]--;
                if(!dp[a][b][0]){
                    dp[a][to][1] = 1;
                    wining[a][to][1] = {a, b, 0};
                    q.push({a, to, 1});
                    used[a][to][1] = true;
                    continue;
                }
                if(!deg[a][to][1])
                    dp[a][to][1] = 0, used[a][to][1] = 1, q.push({a, to, 1});
            }
        }else{
            for(int to : g[a]){
                if(used[to][b][0]) continue;
                if(dp[a][b][1]) deg[to][b][0]--;
                if(!dp[a][b][1]){
                    dp[to][b][0] = 1;
                    q.push({to, b, 0});
                    wining[to][b][0] = {a, b, 1};
                    used[to][b][0] = true;
                    continue;
                }
                if(!deg[to][b][0])
                    dp[to][b][0] = 0, used[to][b][0] = 1, q.push({to, b, 0});
            }
            if(used[a][b][0]) continue;
            if(dp[a][b][1]) deg[a][b][0]--;
            if(!dp[a][b][1]){
                dp[a][b][0] = 1;
                q.push({a, b, 0});
                wining[a][b][0] = {a, b, 1};
                used[a][b][0] = true;
                continue;
            }
            if(!deg[a][b][0])
                dp[a][b][0] = 0, used[a][b][0] = 1, q.push({a, b, 0});
        }

    }
    for(int i = 0; i < n; i++){
        bool ind = true;
        for(int j = 0; j < n; j++)
            ind &= dp[i][j][0];
        if(ind) {
            cur = i;
            return i;
        }
    }
    return -1;
}

int nextMove(int R) {
    cur = wining[cur][R][0].a;
    return cur;
}

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