Submission #97955

#	Time	Username	Problem	Language	Result	Execution time	Memory
97955		SpeedOfMagic	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	545 ms	10616 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
 
const int maxN = 500;
const int M = 2 * maxN * maxN;
vector<int> g[maxN];

int good[M];
unsigned int d[M];
int siz[M];
int pos[M];

//0 if it's officer's turn, 1 if robber's one
int enc(int officerPos, int robberPos, int whoseTurn) {
	return whoseTurn * maxN * maxN + officerPos * maxN + robberPos;
}

inline void expand(int cur) {
	//cout << cur % (maxN * maxN) / maxN << " " << cur % maxN << " " << cur / (maxN * maxN) << siz[cur] << " " << d[cur] << endl;
	assert(d[cur] <= siz[cur]);
	if (d[cur] == siz[cur] || (cur / (maxN * maxN) == 0 && d[cur]))
		good[cur] = pos[cur];
	
	if (good[cur] != -1) {
		assert(good[cur] == -2 || good[good[cur]] != -1);
		int officerPos = cur % (maxN * maxN) / maxN;
		int robberPos = cur % maxN;
		if (cur / (maxN * maxN)) { //robber's turn
			int j = enc(officerPos, robberPos, 0);
			if (good[j] == -1 && officerPos != robberPos) {
				d[j]++;
				pos[j] = cur;
				expand(j);
			}
			for (int i : g[officerPos]) {
				j = enc(i, robberPos, 0);
				if (good[j] == -1 && i != robberPos) {
					d[j]++;
					pos[j] = cur;
					expand(j);
				}
			}
		} else { //officer's turn
			for (int i : g[robberPos]) {
				int j = enc(officerPos, i, 1);
				if (good[j] == -1 && officerPos != i) {
					d[j]++;
					pos[j] = cur;
					expand(j);
				}
			}
		}
	}
}
 
int loc;
int start(int N, bool A[MAX_N][MAX_N]) {
	memset(siz, 0, sizeof siz);
	for (int i = 0; i < M; i++)
		pos[i] = -2;
	memset(good, -1, sizeof good);
	memset(d, 0, sizeof d);
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			if (A[i][j]) 
				g[i].push_back(j);
	
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++) 
			if (i != j) {
				siz[enc(i, j, 0)]++;
				siz[enc(i, j, 0)] += g[i].size();
				siz[enc(i, j, 1)] += g[j].size();
			}
	
	for (int i = 0; i < N; i++) {
		expand(enc(i, i, 0));
		expand(enc(i, i, 1));
	}		
			
	for (int i = 0; i < N; i++) {
		bool no = 0;
		for (int j = 0; j < N; j++)
			no |= good[enc(i, j, 0)] == -1;
		
		if (!no) {
			loc = i;
			return i;
		}
	}
    return -1;
}
 
int nextMove(int R) {
	//cout << loc << " " << R << endl;
	loc = good[enc(loc, R, 0)] % (maxN * maxN) / maxN;
	return loc;
}

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from coprobber.cpp:2:
coprobber.cpp: In function 'void expand(int)':
coprobber.cpp:21:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(d[cur] <= siz[cur]);
         ~~~~~~~^~~~~~~~~~~
coprobber.cpp:22:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (d[cur] == siz[cur] || (cur / (maxN * maxN) == 0 && d[cur]))
      ~~~~~~~^~~~~~~~~~~

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