Submission #143370

#	Time	Username	Problem	Language	Result	Execution time	Memory
143370		Sorting	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	853 ms	8172 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>

using namespace std;

struct Node{
	int x, y;
	bool turn;

	Node(){}
	Node(int x, int y, bool turn){
		this -> x = x;
		this -> y = y;
		this -> turn = turn;
	}
};

int dp[MAX_N][MAX_N][2], movea[MAX_N][MAX_N];
bool used[MAX_N][MAX_N][2];
int cnt[MAX_N][MAX_N];
int n;

int cop;

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 i = 0; i < n; ++i){
    	for(int j = 0; j < n; ++j){
    		movea[i][j] = -1;
    	}
    }

    queue<Node> q;

    for(int i = 0; i < n; i++){
    	int t = 0;
    	for(int j = 0; j < n; j++){
    		if(A[i][j]){
    			t++;
    		}
    	}
    	for(int j = 0; j < n; j++){
    		cnt[j][i] = t;
    	}
    }

    for(int i = 0; i < n; ++i){
    	q.push(Node(i, i, false));
    	q.push(Node(i, i, true));
    	used[i][i][1] = true;
    	used[i][i][0] = true;
    	movea[i][i] = i;
    }

    while(!q.empty()){
    	Node t = q.front();
    	q.pop();

    	//cout << t.x << " " << t.y << " " << t.turn << endl;

    	if(t.turn){
    		for(int i = 0; i < n; ++i){
    			if(A[i][t.x] || i == t.x){
    				if(used[i][t.y][!t.turn]){
    					continue;
    				}
    				used[i][t.y][!t.turn] = true;
    				movea[i][t.y] = t.x; 
    				q.push(Node(i, t.y, !t.turn));
    			}
    		}
    	}
    	else{
    		for(int i = 0; i < n; ++i){
    			if(A[i][t.y]){
    				cnt[t.x][i]--;
    				if(!cnt[t.x][i]){
    					used[t.x][i][!t.turn] = true;
    					q.push(Node(t.x, i, !t.turn));
    				}
    			}
    		}
    	}
    }

    cop = -1;
    for(int i = 0; i < n; ++i){
    	int ok = true;
    	for(int j = 0; j < n; ++j){
    		if(movea[i][j] == -1){
    			ok = false;
    			break;
    		}
    	}
    	if(ok){
    		cop = i;
    	}
    }

    return cop;
}

int nextMove(int R){
	cop = movea[cop][R];

	return cop;
}
/*
g++ "Baltic 14-coprobber.cpp" grader.cpp -std=c++11 -O2 -static -Wall -o coprobber
*/
/*
4
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
0
*/

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