Submission #648220

#	Time	Username	Problem	Language	Result	Execution time	Memory
648220		Ronin13	Cop and Robber (BOI14_coprobber)	C++14	0 / 100	1 ms	336 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

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


void dfs(int v, int u, int ind){
    used[v][u][ind] = true;
    if(ind == 0){
        for(int to : grev[u]){
            if(used[v][to][ind ^ 1]) continue;
            if(dp[v][u][ind]){
                deg[v][to][ind ^ 1]--;
                if(deg[v][to][ind ^ 1] == 0) dp[v][to][ind ^ 1] = 0, dfs(v, to, ind ^ 1);
            }
            if(!dp[v][u][ind]) {
                dp[v][to][ind ^ 1] = true;
                dfs(v, to, ind ^ 1);
            }
        }

    }
    else{
       // grev[v].pb(v);
        for(int to : grev[v]){
            if(used[to][u][ind ^ 1]) continue;
            if(dp[v][u][ind]){
                deg[to][u][ind ^ 1]--;
                if(deg[to][u][ind ^ 1] == 0) dp[to][u][ind ^ 1] = 0, dfs(to, u, ind ^ 1);
            }
            if(!dp[v][u][ind]){
                dp[to][u][ind ^ 1] = true;
                dfs(to, u, ind ^ 1);
            }
        }
        if(used[v][u][ind ^ 1])return;
        if(dp[v][u][ind ^ 1]){
            deg[v][u][ind ^ 1]--;
            if(deg[v][u][ind ^ 1] == 0) dp[v][u][ind ^ 1] = 0, dfs(v, u, ind ^ 1);
        }
        else{
            dp[v][u][ind ^ 1] = 1;
            dfs(v, u, ind ^ 1);
        }
        //grev[v].pop_back();
    }
}



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]) grev[j].pb(i);
		}
	}
	for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            deg[i][j][0] = grev[j].size();
            deg[i][j][1] = grev[i].size() + 1;
        }
	}
	for(int i = 0; i < n; i++){
        dp[i][i][0] = 1;
        dp[i][i][1] = 0;
	}
	for(int i = 0; i < n; i++){
        dfs(i, i, 0);
        dfs(i, i, 1);
	}
    int ans = -1;
    for(int i = 0; i < n; i++){
        bool ind = true;
        for(int j= 0; j < n; j++){
            if(!dp[i][j][0]){
                ind = false;
                break;
            }
        }
        if(ind) {
            cur = i;
            return i;
        }
    }
    return -1;
}

int nextMove(int R) {
    for(int to : grev[cur]){
        if(dp[cur][R][1] == 0){
            return cur;
        }
        if(dp[to][R][1] == 0) {
            cur = to;
            return cur;
        }
    }
}

Compilation message (stderr)

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:89:9: warning: unused variable 'ans' [-Wunused-variable]
   89 |     int ans = -1;
      |         ^~~
coprobber.cpp: In function 'int nextMove(int)':
coprobber.cpp:116:1: warning: control reaches end of non-void function [-Wreturn-type]
  116 | }
      | ^

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